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

发布于 2024-07-09 12:13:52 字数 254 浏览 7 评论 0原文

我理解 Big-O 表示法，但我不知道如何为许多函数计算它。特别是，我一直在试图弄清楚斐波那契序列的简单版本的计算复杂度：

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

斐波那契序列的计算复杂度是多少以及它是如何计算的？

原文

I understand Big-O notation, but I don't know how to calculate it for many functions. In particular, I've been trying to figure out the computational complexity of the naive version of the Fibonacci sequence:

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

What is the computational complexity of the Fibonacci sequence and how is it calculated?

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

懵少女 2024-07-16 12:13:52

您将计算 Fib(n) 的时间函数建模为计算 Fib(n-1) 的时间加上计算 Fib(n-2) 的时间之和) 加上将它们加在一起的时间 (O(1))。这是假设对相同 Fib(n) 的重复评估花费相同的时间 - 即不使用记忆。

T(n<=1) = O(1)

T(n) = T(n-1) + T(n-2) + O(1)

你解决这个递推关系（例如使用生成函数），您最终会得到答案。

或者，您可以绘制深度为 n 的递归树，直观地看出该函数渐近 O(2ⁿ)。然后你可以通过归纳法证明你的猜想。

基数：n = 1 是显而易见的

假设T(n-1) = O(2^n-1< code>)，因此

T(n) = T(n-1) + T(n-2) + O(1) 其中等于

T(n) = O(2^n-1) + O(2^n-2) + O(1) = O(2ⁿ )

但是，正如评论中所述，这不是严格的界限。关于此函数的一个有趣事实是，T(n) 与 Fib(n) 的值渐近相同，因为两者都定义为

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

递归树的叶子将始终返回 1。Fib(n) 的值是递归树中叶子返回的所有值的总和，等于叶子的数量。由于每个叶子节点的计算时间为 O(1)，因此 T(n) 等于 Fib(n) x O(1)。因此，该函数的紧界是斐波那契数列本身 (~θ(1.6ⁿ)）。您可以通过使用我上面提到的生成函数来找出这个紧界。

回复收藏 0 原文

千と千尋 2024-07-16 12:13:52

只需问问自己需要执行多少条语句才能完成 F(n)。

对于F(1)，答案是1（条件的第一部分）。

对于F(n)，答案是F(n-1) + F(n-2)。

那么什么函数满足这些规则呢？尝试 aⁿ (a > 1)：

aⁿ == a^(n-1) + a^{(n-2 )}

除以 a^(n-2)：

a² == a + 1

求解 a，得到 < code>(1+sqrt(5))/2 = 1.6180339887，也称为黄金比例。

所以需要指数时间。

回复收藏 0 原文

π浅易 2024-07-16 12:13:52

我同意 pgaur 和 rickerbh 的观点，递归斐波那契的复杂度是 O(2^n)。

我通过一个相当简单但我相信仍然有效的推理得出了同样的结论。

首先，它是关于计算在计算第 N 个斐波那契数时递归斐波那契函数（从现在起 F() ）被调用的次数。如果序列 0 到 n 中的每个数字被调用一次，那么我们就有 O(n)，如果每个数字被调用 n 次，那么我们就得到 O(n*n) 或 O(n^2)，等等。

因此，当对数字 n 调用 F() 时，对 0 到 n-1 之间的给定数字调用 F() 的次数会随着接近 0 而增加。

作为第一印象，在我看来，如果我们用直观的方式来说，对于给定的数字，每次调用 F() 绘制一个单位，就会得到一种金字塔形状（也就是说，如果我们将单位水平居中）。像这样：

n              *
n-1            **
n-2           ****  
...
2           ***********
1       ******************
0    ***************************

现在的问题是，随着 n 的增长，这个金字塔的底部扩大的速度有多快？

让我们来看一个真实的案例，例如 F(6)

F(6)                 *  <-- only once
F(5)                 *  <-- only once too
F(4)                 ** 
F(3)                ****
F(2)              ********
F(1)          ****************           <-- 16
F(0)  ********************************    <-- 32

我们看到 F(0) 被调用了 32 次，即 2^5，对于这个示例案例来说是 2^(n-1)。

现在，我们想知道 F(x) 到底被调用了多少次，我们可以看到 F(0) 被调用的次数只是其中的一部分。

如果我们在心里将所有从 F(6) 到 F(2) 行的 * 移到 F(1) 行中，我们会看到 F(1) 和 F(0) 行现在长度相等。这意味着，当 n=6 时 F() 被调用的总次数为 2x32=64=2^6。

现在，就复杂性而言：

O( F(6) ) = O(2^6)
O( F(n) ) = O(2^n)

I agree with pgaur and rickerbh, recursive-fibonacci's complexity is O(2^n).

I came to the same conclusion by a rather simplistic but I believe still valid reasoning.

First, it's all about figuring out how many times recursive fibonacci function ( F() from now on ) gets called when calculating the Nth fibonacci number. If it gets called once per number in the sequence 0 to n, then we have O(n), if it gets called n times for each number, then we get O(n*n), or O(n^2), and so on.

So, when F() is called for a number n, the number of times F() is called for a given number between 0 and n-1 grows as we approach 0.

As a first impression, it seems to me that if we put it in a visual way, drawing a unit per time F() is called for a given number, wet get a sort of pyramid shape (that is, if we center units horizontally). Something like this:

n              *
n-1            **
n-2           ****  
...
2           ***********
1       ******************
0    ***************************

Now, the question is, how fast is the base of this pyramid enlarging as n grows?

Let's take a real case, for instance F(6)

F(6)                 *  <-- only once
F(5)                 *  <-- only once too
F(4)                 ** 
F(3)                ****
F(2)              ********
F(1)          ****************           <-- 16
F(0)  ********************************    <-- 32

We see F(0) gets called 32 times, which is 2^5, which for this sample case is 2^(n-1).

Now, we want to know how many times F(x) gets called at all, and we can see the number of times F(0) is called is only a part of that.

If we mentally move all the *'s from F(6) to F(2) lines into F(1) line, we see that F(1) and F(0) lines are now equal in length. Which means, total times F() gets called when n=6 is 2x32=64=2^6.

Now, in terms of complexity:

O( F(6) ) = O(2^6)
O( F(n) ) = O(2^n)

回复收藏 0 原文

疧_╮線 2024-07-16 12:13:52

关于这个麻省理工学院的具体问题有一个非常好的讨论。在第 5 页，他们指出，如果假设加法需要一个计算单元，则计算 Fib(N) 所需的时间与 Fib(N) 的结果密切相关。

因此，您可以直接跳到斐波那契数列的非常接近的近似值：

Fib(N) = (1/sqrt(5)) * 1.618^(N+1) (approximately)

并说，因此，朴素算法的最坏情况性能是

O((1/sqrt(5)) * 1.618^(N+1)) = O(1.618^(N+1))

PS：有一个关于第 N 个斐波那契数列的闭合形式表达式如果您想了解更多信息，请访问维基百科。

There's a very nice discussion of this specific problem over at MIT. On page 5, they make the point that, if you assume that an addition takes one computational unit, the time required to compute Fib(N) is very closely related to the result of Fib(N).

As a result, you can skip directly to the very close approximation of the Fibonacci series:

Fib(N) = (1/sqrt(5)) * 1.618^(N+1) (approximately)

and say, therefore, that the worst case performance of the naive algorithm is

O((1/sqrt(5)) * 1.618^(N+1)) = O(1.618^(N+1))

PS: There is a discussion of the closed form expression of the Nth Fibonacci number over at Wikipedia if you'd like more information.

回复收藏 0 原文

樱花细雨 2024-07-16 12:13:52

您可以将其展开并进行可视化

     T(n) = T(n-1) + T(n-2) <
     T(n-1) + T(n-1) 

     = 2*T(n-1)   
     = 2*2*T(n-2)
     = 2*2*2*T(n-3)
     ....
     = 2^i*T(n-i)
     ...
     ==> O(2^n)

You can expand it and have a visulization

     T(n) = T(n-1) + T(n-2) <
     T(n-1) + T(n-1) 

     = 2*T(n-1)   
     = 2*2*T(n-2)
     = 2*2*2*T(n-3)
     ....
     = 2^i*T(n-i)
     ...
     ==> O(2^n)

回复收藏 0 原文

两相知 2024-07-16 12:13:52

递归算法的时间复杂度可以通过绘制递归树来更好地估计，此时绘制递归树的递推关系为T(n)=T(n-1)+T(n-2)+O(1)
请注意，每个步骤都需要 O(1) 意味着恒定的时间，因为它只对 if 块中的 n 值进行一次比较。递归树看起来像

          n
   (n-1)      (n-2)
(n-2)(n-3) (n-3)(n-4) ...so on

这里让我们说上面树的每个级别都表示由我
因此，

i
0                        n
1            (n-1)                 (n-2)
2        (n-2)    (n-3)      (n-3)     (n-4)
3   (n-3)(n-4) (n-4)(n-5) (n-4)(n-5) (n-5)(n-6)

假设在 i 的特定值处，树结束，这种情况是当 ni=1 时，因此 i=n-1，这意味着树的高度是 n-1。
现在让我们看看树中的 n 层每一层做了多少工作。请注意，正如递归关系中所述，每个步骤都需要 O(1) 时间。

2^0=1                        n
2^1=2            (n-1)                 (n-2)
2^2=4        (n-2)    (n-3)      (n-3)     (n-4)
2^3=8   (n-3)(n-4) (n-4)(n-5) (n-4)(n-5) (n-5)(n-6)    ..so on
2^i for ith level

因为 i=n-1 是树的高度，所以在每个级别完成的工作将为

i work
1 2^1
2 2^2
3 2^3..so on

因此完成的总工作将在每个级别完成的工作之和，因此它将是 2^0+2^1+2^2+2^3 ...+2^(n-1) 因为 i=n-1。
根据几何级数，这个总和是 2^n，因此这里的总时间复杂度是 O(2^n)

Recursive algorithm's time complexity can be better estimated by drawing recursion tree, In this case the recurrence relation for drawing recursion tree would be T(n)=T(n-1)+T(n-2)+O(1)
note that each step takes O(1) meaning constant time,since it does only one comparison to check value of n in if block.Recursion tree would look like

          n
   (n-1)      (n-2)
(n-2)(n-3) (n-3)(n-4) ...so on

Here lets say each level of above tree is denoted by i
hence,

i
0                        n
1            (n-1)                 (n-2)
2        (n-2)    (n-3)      (n-3)     (n-4)
3   (n-3)(n-4) (n-4)(n-5) (n-4)(n-5) (n-5)(n-6)

lets say at particular value of i, the tree ends, that case would be when n-i=1, hence i=n-1, meaning that the height of the tree is n-1.
Now lets see how much work is done for each of n layers in tree.Note that each step takes O(1) time as stated in recurrence relation.

2^0=1                        n
2^1=2            (n-1)                 (n-2)
2^2=4        (n-2)    (n-3)      (n-3)     (n-4)
2^3=8   (n-3)(n-4) (n-4)(n-5) (n-4)(n-5) (n-5)(n-6)    ..so on
2^i for ith level

since i=n-1 is height of the tree work done at each level will be

i work
1 2^1
2 2^2
3 2^3..so on

Hence total work done will sum of work done at each level, hence it will be 2^0+2^1+2^2+2^3...+2^(n-1) since i=n-1.
By geometric series this sum is 2^n, Hence total time complexity here is O(2^n)

回复收藏 0 原文

暮色兮凉城 2024-07-16 12:13:52

证明答案很好，但我总是需要手动进行几次迭代才能真正说服自己。所以我在白板上画了一个小的调用树，并开始计算节点。我将计数分为总节点、叶节点和内部节点。这就是我得到的结果：

IN | OUT | TOT | LEAF | INT
 1 |   1 |   1 |   1  |   0
 2 |   1 |   1 |   1  |   0
 3 |   2 |   3 |   2  |   1
 4 |   3 |   5 |   3  |   2
 5 |   5 |   9 |   5  |   4
 6 |   8 |  15 |   8  |   7
 7 |  13 |  25 |  13  |  12
 8 |  21 |  41 |  21  |  20
 9 |  34 |  67 |  34  |  33
10 |  55 | 109 |  55  |  54

立即跳出来的是叶节点的数量是 fib(n)。经过几次迭代才注意到内部节点的数量是 fib(n) - 1。因此，节点总数为2 * fib(n) - 1。

由于您在对计算复杂性进行分类时丢弃了系数，因此最终答案是 θ(fib(n))。

The proof answers are good, but I always have to do a few iterations by hand to really convince myself. So I drew out a small calling tree on my whiteboard, and started counting the nodes. I split my counts out into total nodes, leaf nodes, and interior nodes. Here's what I got:

IN | OUT | TOT | LEAF | INT
 1 |   1 |   1 |   1  |   0
 2 |   1 |   1 |   1  |   0
 3 |   2 |   3 |   2  |   1
 4 |   3 |   5 |   3  |   2
 5 |   5 |   9 |   5  |   4
 6 |   8 |  15 |   8  |   7
 7 |  13 |  25 |  13  |  12
 8 |  21 |  41 |  21  |  20
 9 |  34 |  67 |  34  |  33
10 |  55 | 109 |  55  |  54

What immediately leaps out is that the number of leaf nodes is fib(n). What took a few more iterations to notice is that the number of interior nodes is fib(n) - 1. Therefore the total number of nodes is 2 * fib(n) - 1.

Since you drop the coefficients when classifying computational complexity, the final answer is θ(fib(n)).

回复收藏 0 原文

芸娘子的小脾气 2024-07-16 12:13:52

它的下端以 2^(n/2) 为界，上端以 2^n 为界（如其他注释中所述）。该递归实现的一个有趣事实是它本身具有 Fib(n) 的紧密渐近界限。这些事实可以总结为：

T(n) = Ω(2^(n/2))  (lower bound)
T(n) = O(2^n)   (upper bound)
T(n) = Θ(Fib(n)) (tight bound)

如果您使用封闭形式，则可以进一步减少紧界喜欢。

It is bounded on the lower end by 2^(n/2) and on the upper end by 2^n (as noted in other comments). And an interesting fact of that recursive implementation is that it has a tight asymptotic bound of Fib(n) itself. These facts can be summarized:

T(n) = Ω(2^(n/2))  (lower bound)
T(n) = O(2^n)   (upper bound)
T(n) = Θ(Fib(n)) (tight bound)

The tight bound can be reduced further using its closed form if you like.

回复收藏 0 原文

扎心 2024-07-16 12:13:52

由于计算中的重复，斐波那契的朴素递归版本在设计上是指数的：

从根本上讲，您正在计算：

F(n) 取决于 F(n-1) 和 F(n-2)

F(n-1) 取决于再次依赖于 F(n-2) 和 F(n-3)

F(n-2) 再次依赖于 F(n-3) 和 F(n-4)

那么你在每个级别都有 2 个浪费的递归调用计算中数据很多，时间函数将如下所示：

T(n) = T(n-1) + T(n-2) + C，其中 C 常数

T(n-1) = T(n -2)+T(n-3)＞ T(n-2)则

T(n)＞ 2*T(n-2)

...

T(n)＞ 2^(n/2) * T(1) = O(2^(n/2))

这只是一个下界，出于分析目的应该足够了，但实时函数是常数的一个因素通过相同的斐波那契公式，封闭形式已知是黄金比例的指数。

此外，您可以使用动态编程找到斐波那契的优化版本，如下所示：

static int fib(int n)
{
    /* memory */
    int f[] = new int[n+1];
    int i;

    /* Init */
    f[0] = 0;
    f[1] = 1;

    /* Fill */
    for (i = 2; i <= n; i++)
    {
        f[i] = f[i-1] + f[i-2];
    }

    return f[n];
}

这是优化的，仅执行n步，但也是指数级的。

成本函数是从输入大小到解决问题的步骤数定义的。当您看到斐波那契的动态版本（n 步骤来计算表格）或了解数字是否为素数的最简单算法（sqrt(n) 来分析有效值）数的约数）。您可能认为这些算法是O(n)或O(sqrt(n))，但事实并非如此，原因如下：
算法的输入是一个数字：n，使用二进制表示法，整数n的输入大小为log2(n)，然后执行的变量变化

m = log2(n) // your real input size

让我们找出步数作为输入大小的函数

m = log2(n)
2^m = 2^log2(n) = n

，那么算法的成本作为输入大小的函数是：

T(m) = n steps = 2^m steps

这就是成本是指数的原因。

The naive recursion version of Fibonacci is exponential by design due to repetition in the computation:

At the root you are computing:

F(n) depends on F(n-1) and F(n-2)

F(n-1) depends on F(n-2) again and F(n-3)

F(n-2) depends on F(n-3) again and F(n-4)

then you are having at each level 2 recursive calls that are wasting a lot of data in the calculation, the time function will look like this:

T(n) = T(n-1) + T(n-2) + C, with C constant

T(n-1) = T(n-2) + T(n-3) > T(n-2) then

T(n) > 2*T(n-2)

...

T(n) > 2^(n/2) * T(1) = O(2^(n/2))

This is just a lower bound that for the purpose of your analysis should be enough but the real time function is a factor of a constant by the same Fibonacci formula and the closed form is known to be exponential of the golden ratio.

In addition, you can find optimized versions of Fibonacci using dynamic programming like this:

static int fib(int n)
{
    /* memory */
    int f[] = new int[n+1];
    int i;

    /* Init */
    f[0] = 0;
    f[1] = 1;

    /* Fill */
    for (i = 2; i <= n; i++)
    {
        f[i] = f[i-1] + f[i-2];
    }

    return f[n];
}

That is optimized and do only n steps but is also exponential.

Cost functions are defined from Input size to the number of steps to solve the problem. When you see the dynamic version of Fibonacci (n steps to compute the table) or the easiest algorithm to know if a number is prime (sqrt(n) to analyze the valid divisors of the number). you may think that these algorithms are O(n) or O(sqrt(n)) but this is simply not true for the following reason:
The input to your algorithm is a number: n, using the binary notation the input size for an integer n is log2(n) then doing a variable change of

m = log2(n) // your real input size

let find out the number of steps as a function of the input size

m = log2(n)
2^m = 2^log2(n) = n

then the cost of your algorithm as a function of the input size is:

T(m) = n steps = 2^m steps

and this is why the cost is an exponential.

回复收藏 0 原文

画骨成沙 2024-07-16 12:13:52

通过绘制函数调用图来计算很简单。只需添加每个 n 值的函数调用，然后查看数字如何增长。

大 O 是 O(Z^n)，其中 Z 是黄金比例或大约 1.62。

随着 n 的增加，莱昂纳多数和斐波那契数都接近这个比率。

与其他 Big O 问题不同，输入没有变化，算法和算法的实现都有明确的定义。

不需要一堆复杂的数学。只需绘制出下面的函数调用，并将函数拟合到数字即可。

或者，如果您熟悉黄金比例，您就会认识到它。

这个答案比公认的答案更正确，该答案声称它将接近 f(n) = 2^n。它永远不会。它将接近 f(n) = gold_ratio^n。

2 (2 -> 1, 0)

4 (3 -> 2, 1) (2 -> 1, 0)

8 (4 -> 3, 2) (3 -> 2, 1) (2 -> 1, 0)
            (2 -> 1, 0)


14 (5 -> 4, 3) (4 -> 3, 2) (3 -> 2, 1) (2 -> 1, 0)
            (2 -> 1, 0)

            (3 -> 2, 1) (2 -> 1, 0)

22 (6 -> 5, 4)
            (5 -> 4, 3) (4 -> 3, 2) (3 -> 2, 1) (2 -> 1, 0)
                        (2 -> 1, 0)

                        (3 -> 2, 1) (2 -> 1, 0)

            (4 -> 3, 2) (3 -> 2, 1) (2 -> 1, 0)
                        (2 -> 1, 0)

It is simple to calculate by diagramming function calls. Simply add the function calls for each value of n and look at how the number grows.

The Big O is O(Z^n) where Z is the golden ratio or about 1.62.

Both the Leonardo numbers and the Fibonacci numbers approach this ratio as we increase n.

Unlike other Big O questions there is no variability in the input and both the algorithm and implementation of the algorithm are clearly defined.

There is no need for a bunch of complex math. Simply diagram out the function calls below and fit a function to the numbers.

Or if you are familiar with the golden ratio you will recognize it as such.

This answer is more correct than the accepted answer which claims that it will approach f(n) = 2^n. It never will. It will approach f(n) = golden_ratio^n.

2 (2 -> 1, 0)

4 (3 -> 2, 1) (2 -> 1, 0)

8 (4 -> 3, 2) (3 -> 2, 1) (2 -> 1, 0)
            (2 -> 1, 0)


14 (5 -> 4, 3) (4 -> 3, 2) (3 -> 2, 1) (2 -> 1, 0)
            (2 -> 1, 0)

            (3 -> 2, 1) (2 -> 1, 0)

22 (6 -> 5, 4)
            (5 -> 4, 3) (4 -> 3, 2) (3 -> 2, 1) (2 -> 1, 0)
                        (2 -> 1, 0)

                        (3 -> 2, 1) (2 -> 1, 0)

            (4 -> 3, 2) (3 -> 2, 1) (2 -> 1, 0)
                        (2 -> 1, 0)

回复收藏 0 原文

月竹挽风 2024-07-16 12:13:52

好吧，根据我的说法，它是 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) ] 的阶数。

Well, according to me to it is O(2^n) as in this function only recursion is taking the considerable time (divide and conquer). We see that, the above function will continue in a tree until the leaves are approaches when we reach to the level F(n-(n-1)) i.e. F(1). So, here when we jot down the time complexity encountered at each depth of tree, the summation series is:

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

that is order of 2^n [ O(2^n) ].

回复收藏 0 原文

命硬 2024-07-16 12:13:52

没有答案强调可能是计算序列的最快且最有效的内存效率方法。斐波那契数列有一个封闭形式的精确表达式。它可以通过使用生成函数或使用线性代数来找到，就像我现在要做的那样。

令 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.v_{n}，其中 M 是 2x2 矩阵由于

M = [0 1]
    [1 1]

f_{n+1} = f_{n+1} 和 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*xx- 的不同解1 = 0。对应的特征值是x_1和x_2。将 M 视为线性变换并更改您的基础以查看它相当于

 D = [x_1  0]
     [0  x_2]

In order to find f_n find v_n and Look at the 第一个坐标。要找到 v_n，请将 M n-1 次应用于 v_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)) 乘法（和加法）运算即可完成此操作。内存复杂性更令人印象深刻，因为它可以通过这样一种方式实现：您始终需要在内存中最多保存 1 个其值小于答案的数字。然而，由于这个数字不是自然数，这里的内存复杂度会根据是否使用固定位来表示每个数字（因此计算时会出现错误）（这种情况下为 O(1) 内存复杂度）或使用更好的模型（例如图灵机，在这种情况下需要进行更多分析。

No answer emphasizes probably the fastest and most memory efficient way to calculate the sequence. There is a closed form exact expression for the Fibonacci sequence. It can be found by using generating functions or by using linear algebra as I will now do.

Let f_1,f_2, ... be the Fibonacci sequence with f_1 = f_2 = 1. Now consider a sequence of two dimensional vectors

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

Observe that the next element v_{n+1} in the vector sequence is M.v_{n} where M is a 2x2 matrix given by

M = [0 1]
    [1 1]

due to f_{n+1} = f_{n+1} and f_{n+2} = f_{n} + f_{n+1}

M is diagonalizable over complex numbers (in fact diagonalizable over the reals as well, but this is not usually the case). There are two distinct eigenvectors of M given by

1      1
x_1    x_2

where x_1 = (1+sqrt(5))/2 and x_2 = (1-sqrt(5))/2 are the distinct solutions to the polynomial equation x*x-x-1 = 0. The corresponding eigenvalues are x_1 and x_2. Think of M as a linear transformation and change your basis to see that it is equivalent to

 D = [x_1  0]
     [0  x_2]

In order to find f_n find v_n and look at the first coordinate. To find v_n apply M n-1 times to v_1. But applying M n-1 times is easy, just think of it as D. Then using linearity one can find

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

Since the norm of x_2 is smaller than 1, the corresponding term vanishes as n tends to infinity; therefore, obtaining the greatest integer smaller than (x_1^n)/sqrt(5) is enough to find the answer exactly. By making use of the trick of repeatedly squaring, this can be done using only O(log_2(n)) multiplication (and addition) operations. Memory complexity is even more impressive because it can be implemented in a way that you always need to hold at most 1 number in memory whose value is smaller than the answer. However, since this number is not a natural number, memory complexity here changes depending on whether if you use fixed bits to represent each number (hence do calculations with error)(O(1) memory complexity this case) or use a better model like Turing machines, in which case some more analysis is needed.

回复收藏 0 原文

~没有更多了~