javascript - Coursera Node.js 斐波那契实现挂起

Question

我目前正在为 coursera 上提供的创业工程类(class)学习 program 2

我正在使用 Amazon Web 服务使用 ubuntu 实例进行编程，但我的编程一直挂起。我的 node.js 程序可能有问题，但我似乎找不到它。

此程序旨在生成前 100 个以逗号分隔的斐波那契数列。

    #! /usr/bin/env node

    //calculation

    var fibonacci = function(n){
                    if(n < 1){return 0;}
                    else if(n == 1 || n == 2){return 1;}
                    else if(n > 2){return fibonacci(n - 1) + fibonacci(n-2);}
            };

    //put in array

    var firstkfib = function(k){
                    var i;
                    var arr = [];
                    for(i = 1; i <= k; i++){
                            arr.push(fibonacci(i));
                    }
            return arr

            };

    //print

    var format = function(arr){
            return arr.join(",");
            };

    var k = 100;
    console.log("firstkfib(" + k +")");
    console.log(format(firstkfib(k)));

我得到的唯一输出是

    ubuntu@ip-172-31-30-245:~$ node fib.js
    firstkfib(100)

然后程序挂了

Answer 1

不知道大家是否熟悉Time complexity和算法分析，但是，事实证明你的程序有一个指数级的运行时间。这基本上意味着，随着输入的增加，运行程序所需的时间呈指数增长。 (如果我解释的不是很清楚，查看this link)

原来这样的运行时间是extremely slow .例如，如果为 k=1 运行程序需要 1 毫秒，需要 2^100 ms为 k=100 运行它.结果是 ridiculously big number .

无论如何，正如哲豪指出的那样，解决方案是保存fib(n-1)的值。和 fib(n-2) (例如，在一个数组中)，并重新使用它来计算 fib(n) .查看麻省理工学院的视频讲座(前 15 分钟)how to do it .