Fibonacci序列的計算復雜性我理解大O表示法，但我不知道如何為許多函數計算它。特別是，我一直試圖找出Fibonacci序列的簡單版本的計算復雜性：int Fibonacci(int n)
{
if (n <= 1)
return n;
else
return Fibonacci(n - 1) + Fibonacci(n - 2);
}斐波納契序列的計算復雜度是多少？它是如何計算的？
3 回答
紅糖糍粑
TA貢獻1815條經驗 獲得超6個贊
Fib(n)Fib(n-1)Fib(n-2)O(1)Fib(n)
T(n<=1) = O(1)
T(n) = T(n-1) + T(n-2) + O(1)
nO(2n)
n = 1
T(n-1) = O(2n-1), 因此
T(n) = T(n-1) + T(n-2) + O(1) 等于
T(n) = O(2n-1) + O(2n-2) + O(1) = O(2n)
Fib(n)
f(n) = f(n-1) + f(n-2).
Fib(n)T(n)Fib(n) x O(1)θ(1.6n)
添加回答
舉報
0/150
提交
取消