指数时间复杂度

Question

Fibonacci的时间复杂度是O(2^n)，如果我想得到3^n的时间复杂度怎么办？

据我的朋友说，fibonacci的时间复杂度是O(2^n)，原因如下：-

return fibonacci(n-1)+fibonacci(n-2)

此外，他还说，如果我们写：-

return fibonacci(n-1)+fibonacci(n-2)+fibonacci(n-3)

有人能说出为什么会这样吗？

根据他的说法，这是因为我们在每一步都要调用Fibonacci函数两次，这就是为什么它是O(2^n)。如果是这样的话，那么以下代码的复杂度应该是O(k^k)，但据我所知，它是O(n)

void permute(int k,int size) {  
    // some base case    
    for (i=k-1;i>=0;i--)          
    permute(k-1,size);  
    return; 
}

他的逻辑在我看来是垃圾。对我来说是2^n因为合并费用。二叉树遍历成本也是如此，尽管函数在每一步调用自己两次，它仍然是O(n)。

谁能告诉我我们之间谁错了，实际的逻辑是什么？

Answer 1

实际上，O(2^n)过高了一点(但仍然正确，因为大-O是一个上限)，it's more like ~θ(1.6^n)。

尝试描绘递归树。每个节点被分割为2，树的深度为n，因此它以O(2^n)结束。

类似地，O(3^ n )示例中，每个节点被分割为3，深度仍为n。

但是对于O(3^n)，我更愿意推荐这样的东西：

someFunction(n)
  if (n == 0)
    return 1
  return someFunction(n-1) + someFunction(n-1) + someFunction(n-1)

当然，这可以通过将最后一个return语句更改为：

return 3*someFunction(n-1)

但这并不是真正的观点(我们也可以计算O(N)中的第n个斐波那契数)。

现在很容易评估。

其中n为1，n-1为3，n-2为3*3，n3为3*3，n3为3*3。

运行时间是O(3^n)。

对于permute函数：

由于要将k-1传递给递归调用(而不是i)，所以对k有1调用，k-1有k-1调用，k-2有(k-1)(k-2)调用，k-3有(k-1)(k-2)(k-3)调用，等等。

这看起来像O((k-1)!)。

如果您要通过i，您将得到1调用k，1表示k-1，1+1=2调用k-2，1+1+2=4表示k-3，1+1+2+4=8调用k-4，16调用k-5，等等。

这看起来像O(2^(k-1))。

二叉树遍历采用O(n)，但n不是二叉树的高度，而是节点数。在Fibonacci示例中，n是高度。如果我们考虑根据高度遍历平衡的二叉树所需的时间，我们还会得到O(2^height)，从一些基本的数学角度来看，它最终成为了O(n)。

Answer 2

这个previous answer会让你相信斐波纳契的序列算法的时间复杂度。

然后，基于同样的答案原则，您的新序列算法可以表示为

T(n) 
= T(n-1) + T(n-2) + T(n-3) 
= ( T(n-2)+T(n-3)+T(n-4) )+( T(n-3)+T(n-4)+T(n-5) )+( T(n-4)+T(n-5)+T(n-6) )
= ...

您可以看到每个节点创建了3个新节点。算法复杂度变成O(3^n)

Wolfram的图像：(考虑节点13到37在下面继续，因为树的底部不是“平面”，因为第一级"n-3“节点将在"n-2”之前完成，在"n-1“之前完成，等等)

​

​