为什么斐波那契数列是大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来计算递归树的高度（当子问题的大小已如答案中所述此处），您似乎总是会发现树的高度是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 the 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.

要理解的技巧实际上很简单：考虑 size 作为输入大小 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 离开。因此，树的 width 为 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），因此作为递归树的一部分，有一个 perfect 高度为 k / 2 的二叉树。如果提取，则该完美子树将具有2 ^{k / 2} 个叶节点。因此，递归树的 width 至少为 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).

关键区别在于：

• 对于分治算法，输入大小为二进制的宽度


• 对于Fibonnaci算法，输入大小是树的高度。

• for divide-and-conquer algorithms, the input size is the width of the binary tree.
• for the Fibonnaci algorithm, the input size is it the height of the tree.

因此，在第一种情况下，树中的节点数为 O（n），但 2 ^ O （n）。相对于输入大小，斐波那契树要大得多。

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.

您提到了大师定理；但是，该定理不能用于分析斐波那契的复杂性，因为它仅适用于在每个递归级别上实际对输入进行划分的算法。斐波那契（Fibonacci）不会不划分输入；实际上，级别 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屋！