为什么斐波那契数列大 O(2^n) 而不是 O(logn)? [英] Why is the Fibonacci Sequence Big O(2^n) instead of O(logn)?

问题描述

我不久前学习了离散数学(在其中我了解了主定理 Big Theta/Omega/O)，但我似乎忘记了 O(logn) 和 O(2^n) 之间的区别(不是在理论意义大哦).我通常理解像合并和快速排序这样的算法是 O(nlogn)，因为它们反复将初始输入数组划分为子数组，直到每个子数组的大小为 1，然后再递归备份树，给出高度为 logn 的递归树+ 1. 但是，如果您使用 n/b^x = 1 计算递归树的高度(当子问题的大小变为 1 时，如答案 here) 似乎你总是得到树的高度是 log(n).

I took discrete math (in which I learned about master theorem, Big Theta/Omega/O) a while ago and I seem to have forgotten the difference between O(logn) and O(2^n) (not in the theoretical sense of Big Oh). I generally understand that algorithms like merge and quick sort are O(nlogn) because they repeatedly divide the initial input array into sub arrays until each sub array is of size 1 before recursing back up the tree, giving a recursion tree that is of height logn + 1. But if you calculate the height of a recursive tree using n/b^x = 1 (when the size of the subproblem has become 1 as was stated in an answer here) it seems that you always get that the height of the tree is log(n).

如果你使用递归来求解斐波那契数列，我认为你也会得到一个大小为 logn 的树，但由于某种原因，算法的大 O 是 O(2^n).我在想，也许不同之处在于你必须记住每个子问题的所有 fib 数才能获得实际的 fib 数，这意味着必须召回每个节点的值，但似乎在合并排序中，每个节点也必须使用(或至少排序).然而，这与二分搜索不同，二分搜索只能根据在树的每个级别进行的比较来访问某些节点，因此我认为这就是混淆的来源.

If you solve the Fibonacci sequence using recursion, I would think that you would also get a tree of size logn, but for some reason, the Big O of the algorithm is O(2^n). I was thinking that maybe the difference is because you have to remember all of the fib numbers for each subproblem to get the actual fib number meaning that the value at each node has to be recalled, but it seems that in merge sort, the value of each node has to be used (or at least sorted) as well. This is unlike binary search, however, where you only visit certain nodes based on comparisons made at each level of the tree so I think this is where the confusion is coming from.

具体来说，是什么导致斐波那契数列与合并/快速排序等算法的时间复杂度不同?

So specifically, what causes the Fibonacci sequence to have a different time complexity than algorithms like merge/quick sort?

推荐答案

其他答案是正确的，但没有说清楚——斐波那契算法和分而治之算法之间的巨大差异从何而来?事实上，两类函数的递归树的形状是相同的——它是一个二叉树.

The other answers are correct, but don't make it clear - where does the large difference between the Fibonacci algorithm and divide-and-conquer algorithms come from? Indeed, the shape of the recursion tree for both classes of functions is the same - it's a binary tree.

理解的技巧实际上非常简单:将递归树的大小视为输入大小n的函数.

The trick to understand is actually very simple: consider the size of the recursion tree as a function of the input size n.

首先回忆一下关于二叉树的一些基本事实:

Recall some basic facts about binary trees first:

• 叶子数n是一棵二叉树，等于非叶子节点数加一.因此二叉树的大小是 2n-1.
• 在完美二叉树中，所有非叶子节点都有两个孩子.
• 具有n个叶子的完美二叉树的高度h等于log(n)，对于随机二叉树:h = O(log(n))，对于退化二叉树h = n-1.

• The number of leaves n is a binary tree is equal to the the number of non-leaf nodes plus one. The size of a binary tree is therefore 2n-1.
• In a perfect binary tree, all non-leaf nodes have two children.
• The height h for a perfect binary tree with n leaves is equal to log(n), for a random binary tree: h = O(log(n)), and for a degenerate binary tree h = n-1.

直观:

• 为了使用递归算法对 n 个元素的数组进行排序，递归树有 n 叶.因此树的宽度是n，树的高度是O(log(n)) 平均，O(n) 最坏情况.

• For sorting an array of n elements with a recursive algorithm, the recursion tree has n leaves. It follows that the width of the tree is n, the height of the tree is O(log(n)) on the average and O(n) in the worst case.

为了使用递归算法计算斐波那契数列元素 k，递归树有 k 层(看看为什么，考虑 fib(k) 调用 fib(k-1)，后者调用 fib(k-2)，依此类推).因此树的高度是k.要估计递归树中节点的宽度和数量的下限，请考虑由于 fib(k) 也调用 fib(k-2)，因此有是高度k/2的完美二叉树，作为递归树的一部分.如果提取，那么完美的子树将有 2^k/2 个叶节点.所以递归树的宽度至少是O(2^{k/2})，或者等价地，2^O(k).

For calculating a Fibonacci sequence element k with the recursive algorithm, the recursion tree has k levels (to see why, consider that fib(k) calls fib(k-1), which calls fib(k-2), and so on). It follows that height of the tree is k. To estimate a lower-bound on the width and number of nodes in the recursion tree, consider that since fib(k) also calls fib(k-2), therefore there is a perfect binary tree of height k/2 as part of the recursion tree. If extracted, that perfect subtree would have 2^k/2 leaf nodes. So the width of the recursion tree is at least O(2^{k/2}) or, equivalently, 2^O(k).

关键的区别在于:

• 对于分治算法，输入大小是二叉树的宽度.
• 对于斐波那契算法，输入大小是树的高度.

因此树中的节点数在第一种情况下为 O(n)，而在第二种情况下为 2^O(n).与输入大小相比，Fibonacci 树大.

Therefore the number of nodes in the tree is O(n) in the first case, but 2^O(n) in the second. The Fibonacci tree is much larger compared to the input size.

您提到了主定理；然而，该定理不能用于分析斐波那契的复杂性，因为它仅适用于输入在每个递归级别实际上划分的算法.斐波那契不分割输入；事实上，i 层的函数为下一层 i+1 产生几乎两倍的输入.

You mention Master theorem; however, the theorem cannot be applied to analyze the complexity of Fibonacci because it only applies to algorithms where the input is actually divided at each level of recursion. Fibonacci does not divide the input; in fact, the functions at level i produce almost twice as much input for the next level i+1.

这篇关于为什么斐波那契数列大 O(2^n) 而不是 O(logn)?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！