我正在阅读SICP。这是我对计算机科学的第一次介绍。
本书在下面介绍了斐波那契算法:
(define (fib n)
(cond
((= n 0) 0)
((= n 1) 1)
(else (+ (fib (- n 1))
(fib (- n 2))))))
[书中提到该算法占用的空间为𝜃 [(n)),而所花费的时间为𝜃 ((φn)]。我理解空间的复杂性,因为它是一棵树的最大深度,但是我似乎无法将时间复杂度的推论付诸实践。
如果您记下每种情况需要花费多少时间(1为常数),
T(0) = 1
T(1) = 1
T(n) = T(n-1) + T(n-2)
您会看到它与斐波那契数完全相同。而且,正如文本(几乎)所说,Fib(n)是𝜃(φn)。