如何显示算法的时间复杂度为O(2^n)?

Question

我正在做一个来自HackerRank硬币找零问题的练习面试题。

我卡住了，正试图理解这个问题的一个解决方案。 这是该问题的递归解决方案（带有我的评论以便理解它）。

  public static int numWays(int[] coins, int sumTo) {
   return numWaysWhichCoin(coins, sumTo, 0);
}
private static int numWaysWhichCoin(int[] coins, int sumTo, int whichCoin) {
    if(sumTo == 0) {
        //empty set
        return 1;
    } else if(sumTo < 0) {
        //no way to form a negative sum with positive coin values
        return 0;
    }  else {
        //sumTo is positive 
        //case gone through all the coins but still a positive sum. Impossible
        if(sumTo > 0 && whichCoin == coins.length) {
            return 0;
        }
        //with and without. With, you can keep using the same coin 
        return numWaysWhichCoin(coins, sumTo - coins[whichCoin], whichCoin) + numWaysWhichCoin(coins, sumTo, whichCoin + 1);
    }
}

作者指出该算法的时间复杂度为O(2ⁿ)。根据我的面试经验，您应该对答案进行证明。如何证明这种时间复杂度呢？在我之前的工作中，为了证明算法运行时间为O(2ⁿ)，我会使用递归关系，例如（斐波那契数列）T(n) = T(n-1) + T(n-2) +c <= 2T(n-1) + c, T(1) = d，但是我无法从这里推导出这样的递归关系。有没有其他方法证明呢？

- committedandroider

---

@DavidEisenstat，gen-y-s的解决方案怎么样？ - committedandroider

该分析给出了界限O((2^n)^(#coins))，这通常是一个相当高的估计。 - David Eisenstat

@DavidEisenstat 但是无论如何，你是怎么知道这个算法的时间复杂度是O(2^n)的呢？ - committedandroider

Answer 1

两个递归调用使它像一个二叉树，以2的n次方速率增长。

就复杂性而言，您的算法与斐波那契递归算法相同。因此，您可以查找并找到许多答案、解释甚至证明，为什么递归斐波那契是2的n次方阶数。

- sivi

---

我知道斐波那契证明。它的T(n) = T(n-1) + T(n-2) + d <= 2T(n-1) + d，这就是我所指的。但在这里，我找不到一个递归关系来限制这个算法。 - committedandroider

是的，谢谢。他们可能不会那么严格。我只是说这类似于斐波那契数列中的两个递归调用模式，并在必要时提供证明。 - committedandroider

不太确定。在斐波那契数列中，n-1和n-2并不是常量（取决于n）。我只是说这些模式在运行时间方面相似。谢谢你的提示！ - committedandroider

但是大O符号表示的是最坏情况，因此您需要证明即使在代码的最佳情况下，您仍将拥有2n，因此您可以假设前两个参数为1并仍然具有2n阶。 - sivi

我不理解你的意思。如果我假设前两个参数为1，则这两个函数调用都将在常数时间内运行，这意味着函数本身将在常数时间内运行。 - committedandroider

Answer 2

假设有R种不同的组合（所请求的结果）。第r个特定解决方案（0≤r≤R-1）中使用第i个硬币（0≤i≤M-1）的硬币数量为C(i, r)。因此，对于0≤r≤R-1中的每个r，我们都有C(0, r)+C(1, r)+...+C(M-1, r)=N。对于每个r，0≤r≤R-1中C(i, r)的最大值是max_c(i)=floor(N/Vi)（Vi是硬币i的价值），它小于或等于N。当i=0..M-1时，c_max(i)的总和<= N*M。因此，在所有组合中使用的单个硬币的总数为O(NM)。您提供的算法简单地迭代了上面组中c_max(i)个单独硬币的所有子组，其时间复杂度为O(2^(NM))。

- gen-y-s

---

我对你使用的符号有点困惑。关于C(0,r)，根据https://www.mathsisfun.com/combinatorics/combinations-permutations.html，这不是意味着从零中选择r个物品吗？ - committedandroider

r是可能的组合（序列）的任意枚举。例如，对于硬币1、2、3和总和为4的情况，组合为(4,0,0)、(3,0,1)、(2,1,0)、(0,2,0)，因此我将这4个组合枚举为0..3。因此，对于第一个组合r=0，我们有C(0,0)=4，C(1,0)=0，C(2,0)=0。 - gen-y-s