math - 确定 (n-1)+(n-1) 的大哦

Question

我一直试图弄清楚这种特殊的复杂性计算，但我读到的关于这种复杂性的所有内容都告诉我它是大 O(2^n) 类型，但是如果我在代码中添加一个计数器并检查有多少它按给定的 n 迭代的次数似乎遵循 4^n 的曲线。也许我只是误解了，因为我放了一个计数++；范围内。

这不是大 O(2^n) 类型的吗？

   public int test(int n) 
   {    
   if (n == 0)
   return 0;
   else
   return test(n-1) + test(n-1);
    }

我将不胜感激任何提示或解释！我对这种复杂性计算完全陌生，这个让我偏离了轨道。

//问候

score 4 · Accepted Answer

int test(int n)
{
    printf("%d\n", n);

    if (n == 0) {
        return 0;
    }
    else {
        return test(n - 1) + test(n - 1);
    }
}

在函数的顶部有一个打印输出，运行test(8)并计算每个打印的次数n会产生这个输出，它清楚地显示了 2 ⁿ的增长。

$ ./test | sort | uniq -c
    256 0
    128 1
     64 2
     32 3
     16 4
      8 5
      4 6
      2 7
      1 8

（uniq -c计算每行出现的次数。0打印 256 次、1128 次等）

也许你的意思是你得到的结果是 O(2 ^{n +1} )，而不是 O(4 ⁿ )？如果你把所有这些数字加起来，你会得到 511，对于n =8，它是 2 ^{n +1} -1。

如果这就是你的意思，那很好。O(2 ^{n +1} ) = O(2⋅2 ⁿ ) = O(2 ⁿ )

score 1 · Accepted Answer

这个函数的复杂度T(n)可以很容易地证明等于c + 2*T(n-1)。由给出的复发

T(0) = 0
T(n) = c + 2*T(n-1)

有它的解决方案 c*(2^n - 1) 或类似的东西。它是 O(2^n)。

现在，如果您将函数的输入大小设为m = lg n，这在这种情况下可能是可以接受的（要表示的位数n，真实输入大小），那么这实际上是一种O(m^4)算法......因为 O(n ^2) = O(m^4)。

score 1 · Accepted Answer

令 x(n) 为的总调用次数test。

x(0) = 1

x(n) = 2 * x(n - 1) = 2 * 2 * x(n-2) = 2 * 2 * ... * 2

总共有 n 个二 - 因此有 2^n 个调用。

score 1 · Accepted Answer

首先：'else' 语句已过时，因为如果 if 计算结果为 true，则 if 已经返回。

关于主题：每次迭代都会分叉 2 次不同的迭代，它们本身会分叉 2 次迭代，等等。因此，对于 n=1，函数被调用 2 次，加上原始调用。对于 n=2，它被称为 4+1 次，然后是 8+1，然后是 16+1 等等。因此复杂度显然是 2^n，因为常数被指数抵消了。

我怀疑您的计数器在两次通话之间没有正确重置。

4 回答 4