algorithm - 指数时间复杂度

Question

斐波那契的时间复杂度是O(2^n)如果我想获得 3^n 的时间复杂度怎么办？

根据我 friend 的说法，由于以下步骤，斐波那契的时间复杂度为 O(2^n):-

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

另外他说，如果我们这样写，它将变成 O(3^n):-

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

谁能告诉我为什么会这样？

根据他的说法，这是因为我们在每一步调用斐波那契函数两次，这就是 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) .

试着想象一棵递归树。每个节点 split 为2，树的深度为n，所以最终大约为O(2^n)。

同理，O(3^n)的例子，每个节点 split 成3，深度还是n。

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

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

当然，这可以通过将最后一个返回语句更改为以下简单地转换为 O(n):

return 3*someFunction(n-1)

但这不是真正的重点(也可以在 O(n) 中计算第 n 个斐波那契数)。

现在很容易评估。

n有1次调用，n-1有3次调用，n-2有3*3次调用，n-3有3*3*3次调用等

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

---

对于 permute 函数:

因为您将 k-1 传递给递归调用(不是 i)，所以您有 1 调用 k，k-1 代表 k-1，(k-1)(k-2) 代表 k-2，(k-1)(k-2)(k -3) 表示 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不是二叉树的高度，而是节点的数量。在斐波那契示例中，n 是高度。如果我们考虑根据高度遍历平衡二叉树需要多长时间，我们最终也会得到 O(2^height)，根据一些基础数学，它最终为O(n)。