2

我一直试图弄清楚这种特殊的复杂性计算,但我读到的关于这种复杂性的所有内容都告诉我它是大 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);
    }

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

//问候

4

4 回答 4

4
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 n的增长。

$ ./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 n )?如果你把所有这些数字加起来,你会得到 511,对于n =8,它是 2 n +1 -1。

如果这就是你的意思,那很好。O(2 n +1 ) = O(2⋅2 n ) = O(2 n )

于 2013-04-16T20:35:41.777 回答
1

这个函数的复杂度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)。

于 2013-04-16T20:43:45.117 回答
1

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

x(0) = 1

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

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

于 2013-04-16T20:36:13.783 回答
1

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

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

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

于 2013-04-16T20:39:59.703 回答