Какая функция фибоначчи будет оцениваться быстрее?

Question

Я пытаюсь получить первые 100 номеров фибоначчи для вывода в .txt-файл. Я запустил его, но это займет некоторое время. Будет ли fibonacci или fibonacci2 быстрее? В приведенном ниже коде используется первый.

#!/usr/bin/env node 

var fs = require('fs'); 

// Fibonacci 
// http://en.wikipedia.org/wiki/Fibonacci_number 
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);} 
}; 

// Fibonacci: closed form expression 
// http://en.wikipedia.org/wiki/Golden_ratio#Relationship_to_Fibonacci_sequence 
var fibonacci2 = function(n) { 
    var phi = (1 + Math.sqrt(5))/2; 
    return Math.round((Math.pow(phi, n) - Math.pow(1-phi, n))/Math.sqrt(5)); 
}; 

// Find first K Fibonacci numbers via basic for loop 
var firstkfib = function(k) { 
    var i = 1; 
    var arr = []; 
    for(i = 1; i < k+1; i++) { 
     var fibi = fibonacci(i); 
     arr.push(fibi); 

     // Print to console so I can monitor progress 
     console.log(i + " : " + fibi); 
    } 
    return arr; 
}; 

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

var k = 100; 

// write to file 
var outfile = "fibonacci.txt"; 
var out = fmt(firstkfib(k)); 
fs.writeFileSync(outfile, out); 
console.log("\nScript: " + __filename + "\nWrote: " + out + "\nTo: " + outfile); 

Answer 1

Это очень наивный способ сделать этот расчет. попытаться сделать что-то вроде:

long[] a = new long[100]; 
a[0] = 1; 
a[1] = 1; 
for (int i = 2; i < 100; ++i) 
{ 
    a[i] = a[i - 2] + a[i - 1]; 
} 

for (int i = 0; i < 100; ++i) 
Console.WriteLine(a[i]); 

Таким образом, вы получаете линейное время O (N)

Answer 2

В общем, рекурсивной функции являются «чище» и «проще» написать, но часто требуют более ressources (в основном память из-за накопления стеков). в вашем случае наилучшим способом получить 100 сначала будет программирование с использованием простого цикла, который будет вычислять следующий номер ряда фибоначчи и добавлять его в список.

double a[100]; 
a[0] = 1; 
a[1] = 1; 
K=2; 
Do{ 

{ 
a[k] = a[k - 2] + a[k- 1]; 
k++; 
}While (k!=100) 

Answer 3

Рекурсивная функция фибоначчи реализована неверно. Правильный способ его рекурсии обсуждается в этой статье Recursion and Fibonacci Numbers. Для тех, кому лень читать, вот их код (это в C, но это не должно быть слишком трудно перевести):

unsigned long fib(unsigned int n) 
{ 
    return n == 0 ? 0 : fib2(n, 0, 1); 
} 

unsigned long fib2(unsigned int n, unsigned long p0, unsigned long p1) 
{ 
    return n == 1 ? p1 : fib2(n - 1, p1, p0 + p1); 
} 

Еще более эффективная реализация будет кэшировать значения последовательности Фибоначчи как это вычисляет их:

var cache = []; 

var fibonacci = function(n) { 
    if(cache.length > n) return cache[n]; 
    return (cache[n] = fib2(n, 0, 1)); 
}; 

var fib2 = function(n, p0, p1) { 
    if(cache.length > n) return cache[n]; 
    return n == 1 ? p1 : (cache[n] = fib2(n - 1, p1, p0 + p1)); 
}; 

я не знаю языка, так что могут быть некоторые проблемы с кодом, но это, по крайней мере, его суть.

Answer 4

По вашему вопросу мы не сможем сделать лучше, чем O (n), так как вам нужно произвести все первые n (n = 100) чисел.

Интересно, что если вам просто нужно число n-го фикса, то существует также решение O (log n).

Алгоритм достаточно прост: Найти п-ю степень матрицы А с использованием подхода разделяй и властвуй и отчет (0,0) -й элемент, где

A = |1  1 | 
    |1  0 | 

Рекурсия будучи

A^n = A^(n/2) * A^(n/2) 

Временная сложность:

T(n) = T(n/2) + O(1) = O(logn) 

Если вы думаете об этом с куском бумаги, вы обнаружите, что т доказательство простое и основано на принципе индукции. Если вам по-прежнему нужна помощь, обратитесь к this link

ПРИМЕЧАНИЕ: Конечно, вы могли бы итерационно рассчитать A, A^2, A^3 и так далее. Однако было бы бессмысленно использовать его по сравнению с другими более простыми решениями, описанными в других ответах. (Из-за явной сложности кода)