前言

一直以为斐波那契数列暴力递归的时间复杂度是，百度了才发现，实际紧界时间复杂度应该是。但其实应该也没错，毕竟求时间复杂度是只要求量级不管系数。

证明

紧界时间复杂度证明

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

但是注意，斐波那契数列的增长率与初项是无关的。证明如下：
设某斐波那契数列的前两项为，令，显然这个数列的增长速度不会超过以为前两项的斐波那契数列。而这个斐波那契数列就是，即
而是个常数，因此斐波那契数列无论初项是多少，渐进增长率都是相同的。
所以的渐进增长率与相同，而，增长率也是一样的

所以
百度可以知道斐波那契数列
所以

量级时间复杂度证明

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

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为将斐波那契数列二叉树补齐成满二叉树，根据这个二叉树，可以得出几个特征：