jumpier ha scritto:
...
Per esempio mi pareva di aver intuito che la complessità della funzione ricorsiva per il calcolo del fattoriale fosse O(n) ... e che la stessa cosa per la funzione iterativa fosse O(1) perché itero nella stessa funzione che eseguo una sola volta fino al termine del calcolo....
Ci sono un po' di pasticci concettuali.
Vediamo alcuni concetti fondamentali:
sia P il problema di risolvere. Il concetto di 'problema' e' molto generale. Qualunque cosa e' un problema! Per ora immagina che P sia una funzione che riceve in ingresso un VETTORE di valori e ritorna in uscita un valore:
r = P(v[N])
sia 'N' la DIMENSIONE del problema.
Gli esempi classici sono:
- 'il problema del commessio viaggiatore: trovare il percorso di lunghezza minima che tocca N citta'
- ordinare N valori
- per il fattoriale, siamo in una situazione tirata per le orecchie. Per ora diciamo che N coincide con il valore di cui si vuole calcolare il fattoriale.
Ovviamente, la soluzione del problema P richiedera' un po' di tempo ed un po' di spazio di memoria. La quantita' del tempo e dello spazio richiesto evidentemente dipendera' da N.
- trovare la strada piu' breve tra 2 citta non richiedera' lo stesso tempo di trovarla tra 1000 citta'
- ordinare 2 valori non richiedere'a lo stesso tempo di ordinarne 1000
- calcolare il fattoriale di 2 non richiede lo stesso tempo di calcolare il fattoriale di 1000
Ora, il problema e': come aumenta il tempo impiegato, lo spazio allocato, in funzione della dimensione N del problema?
Cioe':
- se per trovare la strada minima tra 2 citta' sto 1 secondo (o un nanosecondo, e' lo stesso), per trovarla tra 1000 sto' 1000 secondi? 1000.000 di secondi?, 4 secondi? ...
Qui' entra il gioco il simbolo 'O( f(x) )' che sta' per: 'Ordine di grandezza simile a f(x) '.
La funzione NON VUOLE ESSERE PRECISA, ma indicare un andamento generico che ASSOMIGLIA alla funzione passata come argomento.
Per cui O( f(x) ) E' EQUIVALENTE a O( 1000*f(x) ) ma ANCHE A O( 1.000.000.000*f(x) ): l'ordine di grandexxa e' esattamente lo stesso.
I classici esempi di O( f(x) ) sono:
O(1): ordine di grandezza di una costante (per qualunque valore di n): quindi qualunque sia n, il problema viene risolto sempre nello stesso tempo. Se con n=1 si sta' 't' secondi, con n=2 si sta' sempre 't' secondi, con n=1000, SEMPRE 't' secondi.
O(n): ordine di grandezza lineare. Se con n=1 si sta' 't' secondi, con n=2 si sta' '2t' secondi, con n = 1000, si sta' '1000 t' secondi
O(n^2): ordine di grandezza quadratica. Se con n=1 si sta' 't' secodi, con n=2 si sta' '(2^2) t' == '4 t' secondi. Con n=3 si sta' '9 t' secondi, ecc
O(n^3): stesso ragionamento con oridine di grandezza cubica
O(n^k): (con k costante) stesso ragionamento ma con un andamento simile ad un polinomio di ordine 'k'.
Tutti i problemi che vengono risolti con tempo che hanno una fuzione del tipo O(n^k) sono detti "problemi P", cioe' problemi P)olinomiali
Ma un problema potrebbe essere talmente complicato che il tempo/spazio richiesto per essere risolto NON E' polinomiale, ma che segue una qualche legge esponenziale del tipo:
O( 2^f(n) ) o anche O( e^f(n) ) (come puoi ben immaginare,SONO EQUIVALENTI)
I problemi che NON POSSONO ESSERE risolti in tempo P)olinomiale, sono detti problemi NP (N)ono P)olinomiali).
Un classico esempio e' proprio il problema del commessio viaggiatore che, nel peggiore dei casi, ha una complessita' pari a O(n!) (n fattoriale), che come saprai E' DELLO STESSO ORDINE di O(e^n).
Ora ragiona sui due algoritmi utilizzati per il calcolo del fattoriale:
1) versione iterativa (loop): ovviamente con n=1 il ciclo viene eseguito una volta, con n=10, 10 volti, con n=100, 100 volte. Quindi la complessita TEMPORALE della versione iterativa NON E' COSTANTE, MA LINEARE:
O(n)
2) versione ricorsiva: con l'implementazione classica (f(n)=n*f(n-1)) la ricorsione viene utilizzata:
per n=1, 1 volta, per n=2 2 volte, per n=10, 10 volte. Quindi anche in questo caso la complessita' TEMPORALE E' LINEARE
O(n)
===
Ora ragiona in termini di SPAZIO necessario per calcolare il fattoriale:
1) nella versione iterativa, entri in un ciclo. Ma che esegui il ciclo 1 volta o 1000 volte, lo spazio di memoria utilizzato e' sempre lo stesso. Quindi la complessita' in termini di SPAZIO e' costante:
O(1)
2) nella versione ricorsiva, l'implementazione prevede che la funzione richiama se stessa un certo numero di volte. Ogni volta che una funzione chiama un'altra, seve essere allocato dello spazio sullo stack. Quindi, ovviamente, se la funzione chiama se stessa 1 volta, sullo stack viene allocato spazio per una chiamata di funzione. Ma se chiama se stessa n volte, sullo stack ci deve essere spazio per n chiamate di funzione, una dentro l'altra). Quindi la complessita' SPAZIALE della funzione e?
???