不久前，我参加了离散数学(在其中我学习了主定理Big Theta/Omega/O)，而我似乎忘记了O(logn)和O(2 ^ n)之间的区别(不是从理论上讲大哦)。我一般理解诸如归并和快速排序之类的算法为O(nlogn)，因为它们将初始输入数组重复划分为子数组，直到每个子数组的大小为1，然后递归返回树，从而得到高度为logn的递归树。 +1。但是，如果您使用n/b ^ x = 1来计算递归树的高度(当子问题的大小已如答案here中所述变为1时)，您似乎总会得到树是log(n)。
如果您使用递归求解斐波那契数列，我想您也会得到一棵logn大小的树，但是由于某种原因，该算法的Big O为O(2 ^ n)。我当时在想，可能是因为您必须记住每个子问题的所有fib编号才能获得实际的fib编号，这意味着必须调出每个节点上的值，但是在合并排序中，似乎该值还必须使用(或至少排序)每个节点的。但是，这与二进制搜索不同，在二进制搜索中，您仅基于在树的每个级别进行的比较来访问某些节点，因此我认为这是造成困惑的原因。
因此，具体来说，是什么导致斐波那契序列与诸如合并/快速排序之类的算法具有不同的时间复杂度？
最佳答案
其他答案是正确的，但并不清楚-斐波那契算法和分治法算法之间的巨大差异来自何处？确实，这两种函数的递归树的形状都是相同的-它是一个二叉树。
要理解的技巧实际上非常简单:将递归树的大小视为输入大小n的函数。
首先回想一下有关binary trees的一些基本事实:
n是二叉树，等于非叶子节点的数目加一。因此，二叉树的大小为2n-1。 h叶子的理想二叉树的高度n等于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，因此递归树中有一个高度为O(2^{k/2})的完美二叉树。如果提取，则该完美子树将具有2k/2叶节点。因此，递归树的宽度至少为2^O(k)或等效地为 O(n) 。 关键区别在于:
因此，在第一种情况下，树中的节点数为
2^O(n)，在第二种情况下为i。与输入大小相比，斐波那契树要大得多。你提到Master theorem;但是，该定理不能应用于分析斐波那契的复杂性，因为它仅适用于在每个递归级别上实际划分输入的算法。斐波那契不对输入进行除法；实际上，
i+1级别的函数为下一级别ojit_code产生几乎两倍的输入。关于algorithm - 为什么斐波那契数列是大O(2 ^ n)而不是O(logn)？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/34698842/