2

我目前正在为 coursera 上提供的启动工程课程做计划 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)

然后程序挂起

4

3 回答 3

4

我不知道您是否熟悉时间复杂度和算法分析，但是，事实证明您的程序具有指数运行时间。这基本上意味着，随着输入的增加，运行程序所需的时间呈指数增长。（如果我的解释不是很清楚，请查看此链接）

事实证明，这种运行时间极其缓慢。例如，如果运行您的程序需要 1 毫秒k=1，则2^100 ms运行它需要k=100. 事实证明这是一个大得离谱的数字。

无论如何，正如哲豪指出的那样，解决方案是保存fib(n-1)and的值fib(n-2)（例如，在一个数组中），然后重用它来计算fib(n)。查看麻省理工学院的视频讲座（前 15 分钟），了解如何做到这一点。

于 2013-06-25T23:48:58.907 回答
1

您可能想尝试在计算时打印出数字，而不是在最后打印出整个列表。计算可能挂在沿线的某个地方。

另一方面，这可能是计算斐波那契数列最低效的方法。您计算 fibonacci(n)，然后计算 fibonacci(n+1)，而不重用之前计算中的任何工作。你可能想回去重新考虑你的方法。有一种更快更简单的迭代方法。

于 2013-06-25T23:49:15.010 回答
1

在 nodeJS 中编写密集的计算代码会导致阻塞。因为斐波那契是一个密集的计算代码，所以最终可能会阻塞。

于 2020-11-11T12:51:20.537 回答