Se le versioni iterative e ricorsive di due algoritmi hanno la stessa complessità? Dì ad esempio le versioni iterative e ricorsive della serie di Fibonacci.La versione iterativa e ricorsiva ha la stessa complessità?
La risposta dipende fortemente dalla vostra implementazione. Per l'esempio che hai dato ci sono diverse soluzioni possibili e direi che il modo ingenuo di implementare una soluzione ha una maggiore complessità quando implementato iterativo. Qui i due implementazioni:
int iterative_fib(int n) {
if (n <= 2) {
return 1;
}
int a = 1, b = 1, c;
for (int i = 0; i < n - 2; ++i) {
c = a + b;
b = a;
a = c;
}
return a;
}
int recursive_fib(int n) {
if (n <= 2) {
return 1;
}
return recursive_fib(n - 1) + recursive_fib(n-2);
}
In entrambe le implementazioni ho assunto una corretta ossia l'ingresso n> = 1. Il primo codice è molto più lungo, ma la sua complessità è O (n) cioè lineare, mentre la seconda implementazione è più breve ma ha una complessità esponenziale O (fib (n)) = O (φ^n) (φ = (1+√5)/2) e quindi è molto più lento. Si può migliorare la versione ricorsiva introducendo la memoizzazione (vale a dire ricordando i valori di ritorno della funzione che è già stata calcolata). Questo di solito viene fatto introducendo un array in cui si memorizzano i valori. Ecco un esempio:
int mem[1000]; // initialize this array with some invalid value. Usually 0 or -1
// as memset can be used for that: memset(mem, -1, sizeof(mem));
int mem_fib(int n) {
if (n <= 2) {
return mem[n] = 1;
}
if (mem[n-1] == -1) {
solve(n-1);
}
if (mem[n-2] == -1) {
solve(n-2);
}
return mem[n] = mem[n-1] + mem[n-2];
}
Qui la complessità dell'algoritmo ricorsivo è lineare, proprio come la soluzione iterativa. La soluzione che ho presentato sopra è l'approccio top-down per la soluzione di programmazione dinamica del problema. L'approccio dal basso verso l'alto porterà a qualcosa di molto simile alla soluzione che ho presentato come iterativa. C'è un sacco di articoli sulla programmazione dinamica anche in wikipedia
a seconda dei problemi che ho incontrato nella mia esperienza alcuni sono molto più difficili da risolvere con approccio bottom-up (cioè soluzione iterativa), mentre altri sono difficili da risolvere con approccio top-down. Tuttavia, la teoria afferma che ogni problema che ha una soluzione iterativa ha un ricorsivo con la stessa complessità computazionale (e viceversa).
Spero che questa risposta sia d'aiuto.
nota: non è necessario controllare 'mem [n-2]'. –
'Direi che il modo ingenuo di implementare una soluzione ha una maggiore complessità quando implementato iterativo. Direi che la versione iterativa non è più ingenua. Il problema con la sequenza di Fibonacci è che è terribilmente facile scrivere una versione ricorsiva esponenziale, ma scrivere una versione iterativa esponenziale è difficile, quindi la prima versione si presenta quando la scrittura di un algoritmo iterativo non è davvero ingenua, è necessario aver investito un po 'di pensiero per inventare qualsiasi iterazione. –
Sì, se si utilizzano esattamente le stesse idee sottostanti all'algoritmo, non importa. Tuttavia, la ricorsione è spesso facile da usare per quanto riguarda l'iterazione. Ad esempio, scrivere una versione ricorsiva delle torri di Hanoi è abbastanza facile. Trasformare la versione ricorsiva in una corrispondente versione iterativa è difficile e soggetta ad errori anche se può essere fatta. In realtà c'è un teorema che afferma che ogni algoritmo ricorsivo può essere trasformato in uno equivalente iterativo (per farlo occorre imitare la ricorsione in modo iterativo usando una o più strutture di dati dello stack per mantenere i parametri passati alle invocazioni ricorsive).
Se si utilizza un algoritmo ricorsivo, è possibile convertirlo in iterativo memorizzando tutte le variabili locali della funzione in un array, simulando in modo efficace lo stack sull'heap. Se fatto in questo modo non c'è differenza tra iterativo e ricorsivo.
Si noti che ci sono (almeno) due algoritmi di Fibonacci ricorsivi, quindi per l'esempio per essere esatti è necessario specificare quale algoritmo ricorsivo si sta parlando.
Sì, ogni algoritmo iterativo può essere trasformato in versione ricorsiva e viceversa. Un modo passando le continuazioni e l'altro implementando la struttura dello stack. Questo viene fatto senza aumentare la complessità del tempo.
Se è possibile ottimizzare la ricorsione in coda, ogni algoritmo iterativo può essere trasformato in uno ricorsivo senza aumentare la complessità della memoria asintotica.
Il particolare algoritmo ricorsivo per il calcolo della serie di fibanocci è meno efficiente. consideri la seguente situazione di trovare fib (4) attraverso l'algoritmo ricorsivo
int fib(n) :
if(n==0 || n==1)
return n;
else
return fib(n-1) + fib(n-2)
Ora, quando l'algoritmo di cui sopra viene eseguito per n = 4
fib(4)
fib(3) fib(2)
fib(2) fib(1) fib(1) fib(0)
fib(1) fib(0)
E 'un albero. Dice che per il calcolo di fib (4) è necessario calcolare fib (3) e fib (2) e così via.
Si noti che anche per un valore basso di 4, fib (2) viene calcolato due volte e fib (1) viene calcolato tre volte. Questo numero di aggiunte cresce per grandi numeri.
C'è una congettura che il numero di aggiunte necessarie per il calcolo fib (n) è
fib(n+1) -1
Quindi questa duplicazione è quella che è la causa di prestazioni ridotte in questo particolare algoritmo.
L'algoritmo iterativo per la serie Fibonacci è notevolmente più veloce poiché non prevede il calcolo delle cose ridondanti.
Tuttavia, potrebbe non essere lo stesso per tutti gli algoritmi.
Esistono diversi algoritmi iterativi per il calcolo della sequenza di Fibonacci e di molti ricorsivi, con complessità variabile. –
Penso che si possa ragionevolmente dire che se non hanno la stessa complessità, allora non sono versioni iterative e ricorsive di "lo stesso algoritmo". Sono algoritmi diversi e, naturalmente, algoritmi diversi per calcolare lo stesso risultato non hanno necessariamente la stessa complessità. Detto questo, è abbastanza comune fare riferimento a gruppi di algoritmi correlati con lo stesso nome. Ad esempio quicksort si comporta in modo diverso a seconda di come si sceglie il pivot e da quale ordine si elaborano i due lati della partizione, ma tutte le possibilità sono solitamente chiamate "quicksort". –
... e ne consegue che, indipendentemente dal fatto che due bit di codice possano essere descritti come "lo stesso algoritmo", dipende in alcuni casi dal fatto che il proprio linguaggio/compilatore implementa o meno la ricorsione in coda. Se la versione ricorsiva crea uno stack di chiamate che non è necessario, allora si tratta di un algoritmo diverso con una complessità dello spazio inferiore. –