реализация Coursera Node.js Фибоначчи висят

Question

Я сейчас делаю программу 2 для запуска инженерного курса, предлагаемого на Coursera

Я программирование с использованием и экземпляр убунта с помощью веб-сервисов Amazon и мое программирование постоянно висит. Возможно, что-то не так с моей программой 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 мс, для ее запуска для k=100 потребуется 2^100 ms. Это оказывается ridiculously big number.

В любом случае, как Zhehao указывает, решение, чтобы сохранить значение fib(n-1) и fib(n-2) (в массиве, например), и повторно использовать его для вычисления fib(n). Ознакомьтесь с этой видео-лекцией от MIT (первые 15 минут) по телефону how to do it.

Answer 2

Возможно, вы захотите попробовать распечатать номера по мере их вычисления, а не распечатывать весь список в конце. Возможно, что вычисление висит где-то вдоль линии.

С другой стороны, это, вероятно, самый неэффективный способ вычисления списка чисел фибоначчи. Вы вычисляете fibonacci (n), а затем fibonacci (n + 1) без повторного использования какой-либо работы из предыдущего вычисления. Возможно, вы захотите вернуться и переосмыслить свой метод. Существует гораздо более быстрый и простой итерационный метод.