Big-O per varie implementazioni di Fibonacci

Question

Ho appena provato a implementare il codice (in Java) per vari modi con cui è possibile calcolare l'ennesimo termine della sequenza di Fibonacci e spero di verificare ciò che ho imparato.

L'implementazione iterativa è la seguente:

public int iterativeFibonacci(int n) 
{ 
    if (n == 1) return 0; 
    else if (n == 2) return 1; 
    int i = 0, j = 1, sum = 0; 
    for (; (n-2) != 0; --n) 
    { 
    sum = i + j; 
    i = j; 
    j = sum; 
    } 
    return sum; 
} 

L'implementazione ricorsiva è la seguente: -

public int recursiveFibonacci(int n) 
    { 
    if (n == 1) return 0; 
    else if (n == 2) return 1; 
    return recursiveFibonacci(n-1) + recursiveFibonacci(n-2); 
    } 

L'implementazione memoized è la seguente: -

public int memoizedFibonacci(int n) 
    { 
    if (n <= 0) return -1; 
    else if (n == 1) return 0; 
    else if (n == 2) return 1; 
    if (memory[n-1] == 0) 
     memory[n-1] = memoizedFibonacci(n-1); 
    if (memory[n-2] == 0) 
     memory[n-2] = memoizedFibonacci(n-2); 
    return memory[n-1]+memory[n-2]; 
    } 

I' Ho un po 'di dubbio quando cerco di capire il Big-O di queste implementazioni. Credo che l'implementazione iterativa sia O (n) mentre scorre in N-2 volte.

Nella funzione ricorsiva, ci sono valori ricalcolate, quindi penso sia O (n^2).

Nella funzione memoized, più della metà dei valori è accessibile in base alla memoizzazione. Ho letto che un algoritmo è O (log N) se ci vuole tempo costante per ridurre lo spazio del problema di una frazione e che un algoritmo è O (N) se ci vuole tempo costante per ridurre lo spazio del problema da un importo costante. Ho ragione nel ritenere che l'implementazione memorizzata sia O (n) in complessità? In tal caso, l'implementazione iterativa non sarebbe la migliore tra tutte e tre? (poiché non utilizza la memoria aggiuntiva richiesta dalla memoizzazione).

Answer 1

La versione ricorsiva non è tempo polinomiale - è esponenziale, tightly bounded at φⁿ dove φ è la sezione aurea (≈ 1.618034). La versione ricorsiva utilizzerà la memoria O (n) (l'utilizzo proviene dallo stack).

La versione memoization avrà O (n) tempo alla prima esecuzione, poiché ogni numero viene calcolato solo una volta. Tuttavia, in cambio, prende anche O (n) memoria per l'implementazione corrente (lo n deriva dalla memorizzazione del valore calcolato e anche per lo stack alla prima esecuzione). Se si esegue molte volte, la complessità temporale diventerà O (M + q) dove M è il massimo di tutti gli input n e q è il numero di query. La complessità della memoria diventerà O (M), che proviene dall'array che contiene tutti i valori calcolati.

L'implementazione iterativa è la migliore se si considera una corsa, come viene eseguito anche in O (n), ma utilizza costante quantità di memoria O (1) per calcolare. Per un numero elevato di esecuzioni, esso ricalcola tutto, quindi le sue prestazioni potrebbero non essere buone come la versione di memoizzazione.

(Tuttavia, in pratica, molto prima del problema delle prestazioni e della memoria, è probabile che il numero esagerhi anche i numeri interi a 64 bit, quindi un'analisi accurata deve tenere conto del tempo necessario per aggiungere se si sta eseguendo l'elaborazione il numero completo).

Come plesiv menzionato, il numero di Fibonacci può anche essere calcolato in O (log n) mediante moltiplicazione matriciale (usando lo stesso trucco exponentiation più velocemente dimezzando dell'esponente ad ogni passo).