为什么斐波那契数列大 O(2^n) 而不是 O(logn)？

Question

前段时间学了离散数学（学了主定理，大Theta/Omega/O），好像忘记了O(logn)和O(2^n)的区别（不是在 Big Oh 的理论意义上）。我通常理解像合并和快速排序这样的算法是 O(nlogn) 因为它们重复地将初始输入数组分成子数组直到每个子数组的大小为 1，然后递归返回树，给出一个高度为 logn 的递归树+ 1. 但是，如果您使用 n/b^x = 1 计算递归树的高度（当子问题的大小已变为 1，如答案 here 中所述），似乎您总是得到树的高度是log(n).

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

具体来说，是什么导致斐波那契数列的时间复杂度与 merge/quick 排序等算法不同？

Answer 1

考虑以下实现

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.

Answer 2

据我了解，您推理中的错误是使用递归实现来评估 f(n) 其中 f 表示斐波那契数列，输入大小减少了 2 倍（或一些其他因素），事实并非如此。每次调用（'base cases' 0 和 1 除外）恰好使用 2 次递归调用，因为不可能 re-use 先前计算的值。根据Wikipedia上主定理的表述，递推

f(n) = f (n-1) + f(n-2)

是无法应用主定理的情况。

Answer 3

要解决问题的核心，即 "why Fibonacci and not Mergesort"，您应该关注这个关键区别：

你从 Mergesort 得到的树每层都有 N 个元素，并且有 log(n) 个层。
由于 F(N) 的公式中存在 F(n-1)，因此您从 Fibonacci 得到的树有 N 个级别，并且每个级别的元素数量可能相差很大：它可能非常低（靠近根部，或靠近最低的叶子）或非常高。这当然是因为重复计算相同的值。

要了解我所说的 "repeated computation" 的意思，请查看计算 F(6) 的树：

^{_{斐波那契树图片来自：http://composingprograms.com/pages/28-efficiency.html}}

您看到 F(3) 计算了多少次？

Answer 4

使用递归算法，您有大约 2^N 次斐波那契 (N) 运算（加法）。 那么就是O(2^N).

有了缓存（memoization），你有大约N个操作，然后它是O(N)。

复杂度为 O(N log N) 的算法通常是迭代每个项目 (O(N)) 、拆分递归和合并 ... 拆分2 => 你做了 log N 次递归。

Answer 5

其他答案都对，但没说清楚——斐波那契算法和divide-and-conquer算法之间的巨大差异从何而来？事实上，两个类函数的递归树的形状是相同的——它是一个二叉树。

要理解的技巧其实很简单：将递归树的大小视为输入大小n.

的函数

首先回忆一下关于binary trees的一些基本事实：

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

直觉上：

为了使用递归算法对 n 个元素的数组进行排序，递归树有 n 个叶子 。由此得出树的width为n，树的height平均是O(log(n))，最坏的情况是O(n)。
用递归算法计算一个斐波那契数列元素k，递归树有k层（看看为什么，考虑 fib(k) 调用 fib(k-1)，后者调用 fib(k-2)，依此类推）。由此可知树的高度为k。要估计递归树中节点的宽度和数量lower-bound，考虑由于fib(k)也调用fib(k-2)，因此有完美高度为 k/2 的二叉树作为递归树的一部分。如果提取，该完美子树将有 2^k/2 个叶节点。所以递归树的width至少是O(2^{k/2})或者等价的是2^O(k).

关键区别在于：

对于divide-and-conquer算法，输入大小是二叉树的宽度。
对于斐波那契算法，输入大小是树的高度。

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

你提到Master theorem；但是，该定理不能应用于分析斐波那契的复杂性，因为它仅适用于输入在每个递归级别上实际被划分的算法。斐波那契不划分输入；事实上，级别 i 的功能为下一个级别 i+1 产生几乎两倍的输入。

Answer 6

归并排序时间复杂度为O(n log(n))。快速排序最好的情况是 O(n log(n))，最坏的情况是 O(n^2).

其他答案解释了为什么朴素递归 Fibonacci 是 O(2^n)。

如果您读到 Fibonacci(n) 可以是 O(log(n))，如果使用矩阵法或卢卡斯序列法使用迭代和重复平方计算，这是可能的。卢卡斯序列法示例代码（注意每次循环n除以2）：

/* lucas sequence method */
int fib(int n) {
    int a, b, p, q, qq, aq;
    a = q = 1;
    b = p = 0;
    while(1) {
        if(n & 1) {
            aq = a*q;
            a = b*q + aq + a*p;
            b = b*p + aq;
        }
        n /= 2;
        if(n == 0)
            break;
        qq = q*q;
        q = 2*p*q + qq;
        p = p*p + qq;
    }
    return b;
}

Answer 7

与答案相反，可以应用主定理。但是需要应用递减函数的主定理而不是除函数的主定理。不用带代换的递归关系定理就可以解决，

f(n) = f(n-1) + f(n-2)

f(n) = 2*f(n-1) + c

假设 c 等于 1，因为它是常量并且不影响复杂性

f(n) = 2*f(n-1) + 1

并将此函数代入 k 次

f(n) = 2*[2*f(n-2) +1 ] + 1   
f(n) = 2^2*f(n-2) + 2 + 1


f(n) = 2^2*[2*f(n-3) + 1] +2 + 1 
f(n) = 2^3*f(n-3) + 4 + 2 + 1
.
.
.
f(n) = 2^k*f(n-k) + 2^k-1 + 2^k-2 + ... + 4 + 2 + 1

现在假设 n=k

f(n) = 2^n*f(0) + 2^n-1 + 2^n-2 + ... + 4 + 2 + 1

f(n) = 2^n+1 thus complexity is O(2^n)

检查此 video 以获取递减函数的主定理。

为什么斐波那契数列大 O(2^n) 而不是 O(logn)？

Why is the Fibonacci Sequence Big O(2^n) instead of O(logn)?

sorting

algorithm

tree

recursion