程序的时间复杂度

Question

考虑以下 C 函数：

int f1(int n) {
    if(n == 0 || n == 1)
        return n;
    else 
        return (2 * f1(n-1) + 3 * f1(n-2));
}

我需要找到 f1(n) 的运行时间。

我的解决方案是：

f1(n) 的运行时间的递归关系可以写成：

T(n) = T(n-1) + T(n-2) + c
Where c is a constant
Also T(0) =  T(1) = O(1) {Order of 1 (Constant Time)} 

然后我使用递归树方法来解决这个递推关系。

            ---
             |                   n  -------------------- cost = c     
             |                /     \
             |              n-1      n-2 ---------------- cost = 2c
             |             /  \      /   \
             |           n-2  n-3   n-3  n-4 ------------ cost = 4c
(n-1) levels |           /                 \
             |         ......................
             |        ........................
             |       .........................\
             |      ..........................n-2k
             |      /
            ---    n-k                     

左子树一直延伸到

n-k = 1 => k = n-1

因此，渐近上界为

c+2c+2^2c+2^3c+....+2^(n-1)c
    = Big-Oh(2^n)

同样地，右子树一直延伸到。

n-2k = 1 => k = (n-1)/2

因此，渐近下限为

c+2c+2^2c+2^3c+....+2^((n-1)/2)c
   = Big-Omega(2^(n/2))

由于上限和下限之间的差异是一个函数（而不是一个常数值）

Upper bound = 2^n =  2^(n/2) * 2^(n/2)
Lower bound = 2^(n/2)

所以在我看来，我不能写成T(n) = Theta(2^n)。

但是这个问题的答案是时间复杂度为Theta(2^n)。

那么我做错了什么？

- abnvanand

---

既然theta是上限，那么它与下限的差异有什么关系呢？ - Richard

实际上，Theta既属于O又属于Omega，即它是上限和下限。 - gue

Answer 1

这段文字的意思是：“这个循环等同于斐波那契数列，维基百科上有很多关于这个循环的信息。斐波那契数列的时间复杂度为O(2^n)，下限为Omega(2^(n/2))。还有一些相关问题提到了这些界限，以及约为θ(1.6n)的紧密界限。”

- gue

Answer 2

只有最后一层被计算。 其他层只是调用下一层。

- Zeta