我不知道这个算法中的数学,可以使用一些帮助。
算法:
if n<2 then
return n
else return fibonacci(n-1) + fibonacci(n-2)
陈述
n < 2 是 O(1)
时间 n >=2 是 O(1)
返回 n 是 O(1) 时间 n>=2 是 - 返回 fib(n-1) + fib(n-2) 是 -
时间 n>=2 为 T(n-1) + T(n-2) +O(1)
总计: O(1) T(n-1) + T(n-2) + O(1)
T(n) = O(1) 如果 n < 2
T(n) = T(n-1) + T (n-2) + O(1) 如果 n>=2