SICP：我很难理解斐波那契算法的时间复杂度

Question

我正在阅读SICP。这是我第一次接触计算机科学。

本书介绍了下面的斐波那契算法：

(define (fib n)
(cond 
((= n 0) 0)
((= n 1) 1)
(else (+ (fib (- n 1)) 
(fib (- n 2))))))

书中提到，该算法占用的空间是θ(n(，花费的时间是θ(φⁿ(。我理解空间复杂性，因为它是一棵树的最大深度，但我似乎无法理解时间复杂性是如何得出的。

Answer 1

如果你写下每种情况下需要多少时间(1 是常数(，

T(0) = 1
T(1) = 1
T(n) = T(n-1) + T(n-2)

你会看到它与斐波那契数完全相同。
正如文本(几乎(所说，Fib(n( 是 θ(φⁿ(。