求时间复杂度

Question

int f(int n) { if( n == 1 || n == 2) return n; else return f(n - 1) + f(n - 2)+1; }

Answer 1

和斐波那契数列的复杂度相同。

设 f(n) 需时间 T(n)，由 f(n) = f(n-1) + f(n-2) + 1 得
T(n) = T(n-1) + T(n-2) + 1
T(n-1) 和 T(n-1) 为至少为 n 的一次方，所以常数1忽略不计。
T(n) = T(n-1) + T(n-2)
< T(n-1) + T(n-1) = 2T(n-1)
< 2*2T(n-2)
<(2^i)T(n-i)
<(2^(n-2))T(n-(n-2))=(2^(n-2))T(2)=2^(n-2)
所以时间复杂度为 2^n。