时间复杂度 - 错误的递归 - British Change Combinations

Question

我最近想出了一个解决英国零钱问题（即有多少硬币组合可以产生给定总数）的幼稚（+糟糕）解决方案。我现在 a better solution，但仍然对解决以下两个解决方案的时间和 space 复杂性感兴趣。

最差的解决方案

此解决方案递归地尝试将每个数字与自身和每个其他数字相结合，从而导致大量重复工作。我相信这是 O(n^n) 时间并且不确定如何衡量 space 复杂性（但它很大，因为我们正在存储每个结果）。想法？

var makeChange = function(total){ // in pence
  var allSets = new Set();
  var coins = [1,2,5,10,20,50,100,200];

  var subroutine = (arr, total) => {
    if(total < 0){ return; }
    if(total === 0){
      allSets.add(''+arr);
    } else {
      // increase each coin amount by one and decrease the recursive total by one
      for(var i = 0; i<coins.length; i++){
        if((total - coins[i]) >= 0){
          subroutine(arr.slice(0,i).concat(arr[i]+1).concat(arr.slice(i+1)), (total - coins[i]))
        }
      }
    }
  };

  var zeros = new Array(coins.length).fill(0);
  subroutine(zeros, total);
  return allSets.size;
};

改进的解决方案

这个解决方案仍然具有巨大的 space 复杂度，但我相信时间复杂度已经 - 改进 - 到 O(n!) 因为我们每次都在较小的硬币子集上递归。

var makeChange = function(total){ // in pence
  var allSets = new Set();
  var coins = [1,2,5,10,20,50,100,200];

  var subroutine = (arr, total, start) => {
    if(total < 0){ return; }
    if(total === 0){
      console.log(''+arr);
      allSets.add(''+arr);
    } else {
      // only solve for coins above start, since lower coins already solved
      for(var i = start; i<coins.length; i++){
        if((total - coins[i]) >= 0){
          subroutine(arr.slice(0,i).concat(arr[i]+1).concat(arr.slice(i+1)), (total - coins[i]), i);
        }
      }
    }
  };

  var zeros = new Array(coins.length).fill(0);
  for(let i = 0; i<coins.length; i++){
    subroutine(zeros, total, i);
  }

  return allSets.size;
};

请帮助我了解我的 time/space 复杂性估计是否正确，以及如何更好地估计此类未来问题。谢谢！

Answer 1

第一个算法的复杂度实际上不是O(n^n)。 N 是代表您输入的变量。在这种情况下，我将引用变量 "total" 作为您的输入，因此 N 是基于总计的。为了使您的算法成为 O(n^n)，它的递归树必须具有 N 的深度和 N 的分支因子。在这里，您的递归深度基于硬币数组中的最小变量。您的递归树有一个分支，您只需每次减去该值并递归直到总计为零。鉴于该值是常数，可以安全地说你的深度是 n。您的递归树的分支因子也基于您的 coins 数组或其中的值数。对于每个函数调用，您都会生成 C 个其他函数调用，其中 C 是您的硬币数组的大小。这意味着你的函数实际上是 O(n^c) 而不是 O(n^n)。您的时间和 space 复杂性都取决于您的硬币数组的大小以及您输入的数字。

您的函数的 space 复杂度为 O(n^c * c)。每次你调用你的函数时，你也会根据你的输入传递一个大小的数组。我们已经证明有 O(n^c) 次调用，并且每次调用都包含一个大小为 c 的数组。

记住在分析函数的复杂性时要考虑所有输入。

时间复杂度 - 错误的递归 - British Change Combinations

Time Complexity - Bad Recursion - British Change Combinations

javascript

algorithm

recursion

time-complexity

coin-change