前言

一直以为斐波那契数列暴力递归的时间复杂度是$O(2^{n})$，百度了才发现，实际紧界时间复杂度应该是$O((\frac{1+\sqrt{5}}{2})^{n})$。但其实$O(2^{n})$应该也没错，毕竟求时间复杂度是只要求量级不管系数。

证明

紧界时间复杂度证明

斐波那契数列的计算过程很简单。就是简单的$F(n) = F(n-1) + F(n-2)$
我们把计算$F(i)$所需的时间记为$T(i)$。然后记计算加法所需的时间为1，那么显然有$T(n) = 1+ T(n-1) + T(n-2)$
这一式子可以进行变形。两边同时加 1，得到$T(n)+1 = (T(n-1)+1) + (T(n-2)+1)$
记$A(n) = T(n) + 1$，显然有$A(n) = A(n-1) + A(n-2)$
明显这是一个斐波那契数列，只不过初项有所不同

但是注意，斐波那契数列的增长率与初项是无关的。证明如下：
设某斐波那契数列的前两项为$a, b$，令$c = max(a, b)$，显然这个数列的增长速度不会超过以$c, c$为前两项的斐波那契数列。而这个斐波那契数列就是$c, c, 2c, 3c, 5c, 8c, …, F(n)c$，即$c(1, 1, 2, 3, 5, 8, …, F(n))$
而$c$是个常数，因此斐波那契数列无论初项是多少，渐进增长率都是相同的。
所以$A(n)$的渐进增长率与$F(n)$相同，而$T(n) = A(n) - 1$，增长率也是一样的

所以$T(n) ∈ O(F(n))$
百度可以知道斐波那契数列$F(n) = \frac{1}{\sqrt{5}}[(\frac{1+\sqrt{5}}{2})^{n}-(\frac{1-\sqrt{5}}{2})^{n}]$
所以$T(n) ∈ O((\frac{1+\sqrt{5}}{2})^{n})$

量级时间复杂度证明

我们可以根据函数递归执行顺序画出下图的二叉树结构（假设求第五个斐波那契数）

graph TD
A(("F(5)")) --> B(("F(4)"))
A(("F(5)")) --> C(("F(3)"))
B(("F(4)")) --> D(("F(3)"))
B(("F(4)")) --> E(("F(2)"))
C(("F(3)")) --> F(("F(2)"))
C(("F(3)")) --> G(("F(1)"))
D(("F(3)")) --> H(("F(2)"))
D(("F(3)")) --> I(("F(1)"))
E(("F(2)")) --> J("X")
E(("F(2)")) --> K("X")
F(("F(2)")) --> L("X")
F(("F(2)")) --> M("X")
G(("F(1)")) --> N("X")
G(("F(1)")) --> O("X")

带X为将斐波那契数列二叉树补齐成满二叉树，根据这个二叉树，可以得出几个特征：

满二叉树层数为$n-1$，这里$n=5$，所以有4层
满二叉树第h层（第1层为首层）个数为$2^{h-1}$
满二叉树总结点数为$2^{n-1}-1$，这里$n=5$，所以满二叉树结点为15
斐波那契数列二叉树总结点数为$2^{n-2}+1$，这里$n=5$，斐波那契数列二叉树总结点数为9

所以这个时间复杂度就是$O(2^{n-2}+1) = O(2^{n})$