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

我一直试图绕过这种复杂性计算，但是我所读到的有关这种复杂性的所有信息都告诉我，它的类型为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);
    }

我希望对此有任何提示或解释!我对这种复杂性计算完全陌生，而这使我偏离了轨道。

//问候

最佳答案

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

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

在函数顶部显示打印输出后，运行test(8)并计算每个n的打印次数即可产生此输出，该输出显然增长了2n。

$ ./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次，1 128次，等等。)

也许您是说您得到的结果是O(2n + 1)，而不是O(4n)？如果将所有这些数字加起来，您将得到511，对于n = 8，它是2n + 1-1。

如果那是您的意思，那很好。 O(2n + 1)= O(2⋅2n)= O(2n)

关于math - 确定(n-1)+(n-1)的大哦，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/16046484/