javascript - 使用两个循环进行更改的时间复杂度 - javascript

Question

以下函数的时间复杂度是多少，该函数返回给定硬币的值(value)和面额(即镍币、 Angular 币等)可以进行找零的方式的数量？我的回答是它是 o(n) 因为第二个循环本质上是“缓存”你正在查看的值，为了清楚起见，你可以在没有它的情况下编写这个函数。然而，当我看到两个 for 循环时，我总是倾向于想到 o(n^2)。变量 j 是不是几乎像一个临时变量并且独立于“i”运行？

var makeChange = function (value, denoms) {
  var changeCounts = { 0: 1};

  for (var i = 0; i < denoms.length; i++) {
    for (var j = denoms[i]; j <= value; j++) {
      var remainder = j - denoms[i];
      if (changeCounts[j]) {
        changeCounts[j] += changeCounts[remainder];
      } else {
        changeCounts[j] = changeCounts[remainder];
      }
    }
  }

  return changeCounts[value];
}

Answer 1

让我们将问题陈述框定为:

给定一个值 N，如果我们想找零 N 美分，并且我们有无限供应的每个 S = { S1, S2, .. , Sm} 值(value)的硬币，我们有多少种找零的方法？硬币的顺序无关紧要。

例如，对于 N = 4 和 S = {1,2,3}，有四种解决方案:{1,1,1,1}，{1,1,2}，{2,2}， {1,3}。所以输出应该是4。对于N = 10和S = {2, 5, 3, 6}，有五种解决方案:{2,2,2,2,2}，{2,2,3,3}， {2,2,6}、{2,3,5} 和 {5,5}。所以输出应该是 5。

在您的代码中，在外层循环中，您将遍历所有面额 (0 < i <= m-1)。 在内部循环中，您从 S[i] 迭代到求和 n。现在让我们考虑最坏的情况。假设您有 S = {1, 2, 3, 4, 5} 和 N = 1000。

在外循环的第一次迭代中，当 i = 0 时，您的内循环将从 1 迭代到 1000。 当 i = 1 时，您的外循环将从 2 迭代到 1000。类似地，对于内循环的第 i 次迭代，您的外循环将从 i+1 迭代到 1000。

所以我们在这种情况下迭代了 1000 + 999 + 998 + 997 + 996 = 4990 次，几乎等于 5000 次，基本上是 N x M。

在计算算法复杂性时，我们总是必须考虑最坏的情况。因此，您的解决方案的时间复杂度为 O(mn)，其中 n 是总找零，m 是可用面额的数量。