为什么斐波那契序列大O（2 ^ n）而不是O（logn）？
前一段时间，我学习了离散数学（我在其中学到了有关主定理的Big Theta / Omega / O），我似乎忘记了O（logn）和O（2 ^ n）之间的区别（不是理论上的大哦）。 我通常理解合并和快速排序等算法是O（nlogn），因为它们将初始输入数组重复划分为子数组，直到每个子数组的大小为1，然后递归备份树，从而得到一个高度为logn的递归树+ 1.但是，如果使用n / b ^ x = 1来计算递归树的高度（当子问题的大小变为1时，就像在这里回答中所述），似乎你总是得到树是log（n）。
如果你用递归求解斐波那契数列，我会认为你也会得到一个大小为logn的树，但由于某种原因，算法的大O是O（2 ^ n）。 我在想，也许差别是因为你必须记住每个子问题的所有fib数以得到实际的fib数，这意味着每个节点的数值必须被回想，但似乎在合并排序中，数值的每个节点也必须被使用（或者至少被分类）。 这与二分查找不同，但是，您只能根据树的每个级别进行比较来访问某些节点，所以我认为这是混淆的来源。
特别是，什么导致斐波纳契数列与合并/快速排序算法有不同的时间复杂度？
其他答案是正确的，但不要说清楚 - 斐波那契算法和分而治之算法之间的巨大差异来自哪里？ 实际上，两类函数的递归树的形状都是相同的 - 它是一棵二叉树。
要理解的技巧其实很简单：将递归树的大小视为输入大小n的函数。
先回想一下关于二叉树的一些基本事实：
n是二叉树的叶n等于非叶节点数加1。 二叉树的大小因此是2n-1。 n叶子的二叉树的高度h等于log(n) ： h = O(log(n)) ，对于简并二叉树h = n-1 。 直观：
为了用递归算法对n元素的数组进行排序，递归树具有n 叶子 。 因此，树的宽度为n ，树的高度平均为O(log(n)) ，最坏情况下为O(n) 。
用于计算斐波纳契数列元件k与递归算法，递归树具有k 水平 （明白为什么，考虑fib(k)调用fib(k-1)它调用fib(k-2)依此类推） 。 因此树的高度是k 。 为了估计递归树中节点的宽度和数量的下限，考虑到由于fib(k)也称为fib(k-2) ，所以有一个高度为k/2的完美二叉树作为递归树。 如果提取出来，那个完美的子树就会有2k / 2个叶子节点。 所以递归树的宽度至少为O(2^{k/2})或者等价于2^O(k) 。
关键的区别是：
因此，树中节点的数量在第一种情况下为O(n) ，而在第二种情况下为2^O(n) 。 斐波那契树比输入大小要大得多。
你提到大师定理; 然而，该定理不能用于分析斐波纳契的复杂性，因为它只适用于输入在递归的每个级别被实际分割的算法。 斐波那契不会分割输入; 实际上，在电平的功能的i产生几乎两倍为下一级多输入i+1 。
为了解决这个问题的核心问题，那就是“为什么是斐波那契而不是合并”，你应该关注这个关键的区别：
通过“重复计算”来查看我的意思，查看F（6）的计算树：
斐波纳契树图片来自：http://composingprograms.com/pages/28-efficiency.html
你看到F（3）被计算多少次？
考虑下面的实现
int fib(int n)
{
if(n < 2)
return n;
return fib(n-1) + fib(n-2)
}
我们用T（n）表示fib执行的计算fib(n) 。 由于fib(n)调用fib(n-1)和fib(n-2) ，这意味着T（n）至少为T(n-1) + T(n-2) 。 这又意味着T(n) > fib(n) 。 有一个直接的公式fib(n) ，它对于n的幂是不变的。 因此T（n）至少是指数的。 QED。
上一篇: Why is the Fibonacci Sequence Big O(2^n) instead of O(logn)?