斐波那契数列的计算复杂度

Question

斐波那契数列的计算复杂度

time-complexitybig-ocomplexity-theoryfibonacci

395

我理解大O符号，但不知道如何计算许多函数的复杂度。特别是，我一直在尝试弄清楚斐波那契数列的朴素版本的计算复杂度：

int Fibonacci(int n)
{
    if (n <= 1)
        return n;
    else
        return Fibonacci(n - 1) + Fibonacci(n - 2);
}

斐波那契数列的计算复杂度是多少，如何计算？

- Princess

7

这里有一些不错的答案。 - Greg

3

请查看这里的矩阵形式部分：http://en.wikipedia.org/wiki/Fibonacci_number。通过以巧妙的方式计算矩阵 ^ n，您可以在O(lg n)的时间内计算斐波那契数列中的第n项Fib(n)。诀窍在于进行幂函数计算。有一个非常好的iTunesU讲座专门介绍如何在O(lg n)的时间内解决这个问题。该课程是MIT的算法入门第三讲（完全免费，如果您感兴趣，请查看）。 - Aly

1

以上两条评论都没有回答问题，问题是关于朴素版本（在发布的代码中）的计算复杂度，而不是像矩阵形式或非递归计算这样更聪明的版本。 - Josh Milthorpe

这里有一个非常好的视频（链接：https://youtu.be/pqivnzmSbq4），讲解了递归实现的下限复杂度（2^n/2）和上限复杂度（2^n）。 - RBT

1

一个旁注的问题：斐波那契数列的__naive__实现应该是__iterative__还是__recursive__？ - RBT

12个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Fırat Kıyak · Answer 1

没有答案能够强调计算这个序列最快且最节省内存的方法。对于斐波那契数列存在一个闭式精确表达式，可以通过使用生成函数或线性代数来找到，接下来我将介绍如何实现。

设 f_1,f_2, ... 是斐波那契数列，其中 f_1 = f_2 = 1。现在考虑一个二维向量序列

f_1  ,  f_2  ,  f_3  ,  ...
f_2  ,  f_3  ,  f_4  ,  ...

观察向量序列中的下一个元素v_{n+1}，其中M是一个2x2矩阵，给定为M.v_{n}。

M = [0 1]
    [1 1]

由于 f_{n+1} = f_{n+1} and f_{n+2} = f_{n} + f_{n+1}

M 在复数上是对角化的（实际上在实数上也是对角化的，但通常不是这种情况）。M 的两个不同特征向量为

1      1
x_1    x_2

其中x_1 = (1+sqrt(5))/2，x_2 = (1-sqrt(5))/2是多项式方程x*x-x-1 = 0的不同解。相应的特征值为x_1和x_2。将M视为线性变换并更改基础来查看它等效于

 D = [x_1  0]
     [0  x_2]

为了找到 f_n，请找到 v_n 并查看第一个坐标。要找到 v_n，请将 M 应用于 v_1 n-1 次。但是，应用 M n-1 次很容易，只需将其视为 D。然后使用线性性即可找到

f_n = 1/sqrt(5)*(x_1^n-x_2^n)

由于x_2的范数小于1，随着n趋近于无穷大，相应的项会消失；因此，只需获得比(x_1^n)/sqrt(5)小的最大整数即可准确找到答案。通过利用重复平方的技巧，这可以仅使用O(log_2(n))乘法（和加法）操作来完成。内存复杂度更为惊人，因为它可以以一种方式实现，您始终只需要在内存中保存一个值小于答案的数字。但是，由于该数字不是自然数，因此此处的内存复杂度取决于是否使用固定位来表示每个数字（因此进行带误差的计算）（在这种情况下为O(1)内存复杂度），或者使用像图灵机这样的更好的模型，在这种情况下需要进行更多的分析。

- pgaur · Answer 2

根据我的看法，这个函数的时间复杂度是O(2^n)，因为在这个函数中只有递归需要考虑时间（分治）。我们可以看到，上述函数将一直延伸到树的叶子节点，直到我们到达级别F(n-(n-1))即F(1)。因此，在这里，当我们记录树的每个深度遇到的时间复杂度时，总和系列为：

1+2+4+.......(n-1)
= 1((2^n)-1)/(2-1)
=2^n -1

这是 2^n [ O(2^n) ] 的顺序。