Come s calcola complessità algoritmica iterazione/ricorsione
Buongiorno,
vorrei capire come si calcola la complessità di una funzione fornita in Pseudocodice.
So che ogni istruzione ha un suo peso, come per esempio i cicli for hanno un costo $ o(n^2) $ .
Però so che la questione cambia a seconda se si hanno davanti funzioni iterative o ricorsive.
Sareste in grado di darmi una panoramica generale su come agire di fronte alle due tipologie di funzioni per calcolare la complessità?
Vi ringrazio sin da ora.
vorrei capire come si calcola la complessità di una funzione fornita in Pseudocodice.
So che ogni istruzione ha un suo peso, come per esempio i cicli for hanno un costo $ o(n^2) $ .
Però so che la questione cambia a seconda se si hanno davanti funzioni iterative o ricorsive.
Sareste in grado di darmi una panoramica generale su come agire di fronte alle due tipologie di funzioni per calcolare la complessità?
Vi ringrazio sin da ora.
Risposte
Un ciclo for NON ha complessità $o(n^2)$. La tua domanda è in ogni caso un po' troppo ampia e ti consiglio caldamente di andarti a leggere i primi capitoli di un buon testo di algoritmi. Potremmo infatti solo farti qualche esempio o piccola tecnica di calcolo, ma non è possibile riassumere tutta la teoria in un post di un forum.
Ho sbagliato a scrivere.
Intendevo dire che un ciclo for, per esempio, va calcolato come un'istruzione che viene eseguita "n" volte, quindi ha costo "n".
In ogni caso, vorrei almeno capire la differenza tra un approccio con funziona ricorsiva e uno con funzione iterativa.
Intendevo dire che un ciclo for, per esempio, va calcolato come un'istruzione che viene eseguita "n" volte, quindi ha costo "n".
In ogni caso, vorrei almeno capire la differenza tra un approccio con funziona ricorsiva e uno con funzione iterativa.
Il caso iterativo lo hai capito, si tratta di moltiplicare il numero di istruzioni per il numero dei cicli che vengono svolti.
Nel caso ricorsivo si considera inizialmente la complessità computazionale di una chiamata di funzione.
Supponiamo che questa funzione ricorsiva divida a metà il problema (di dimensione [tex]n[/tex]) ad ogni chiamata, e scarti una delle due metà. Allora il costo [tex]T[/tex] dell'algoritmo sarà [tex]T(n)=T(\frac{n}{2}) + C[/tex], dove C è il costo della chiamata a cui è aggiunto il costo della chiamata ricorsiva.
Ma [tex]T(\frac{n}{2})=T(\frac{n}{4})+C[/tex], da cui [tex]T(n)=(T(\frac{n}{4})+C) + C)=T(\frac{n}{4})+2C[/tex].
Procedendo in maniera analoga risulterà sempre che [tex]T(n)=T(\frac{n}{2^{i}})+i\cdot c[/tex]
Vogliamo fermarci alla chiamata base, di costo [tex]T(1)[/tex], che si ha quando [tex]\frac{n}{2^{i}}=1[/tex] ovvero quando [tex]i=\log_{2}n[/tex].
Sostituendo nella formula di [tex]T(n)[/tex] troviamo [tex]T(n)=T(1)+c\log_{2}n=O(\log n)[/tex], se [tex]T(1)[/tex] è costante.
Si tratta del caso più semplice, esistono pacchi di altre situazioni in cui può essere utile il Teorema Master, o ancora altri metodi di risoluzione delle relazioni di ricorrenza.
Nel caso ricorsivo si considera inizialmente la complessità computazionale di una chiamata di funzione.
Supponiamo che questa funzione ricorsiva divida a metà il problema (di dimensione [tex]n[/tex]) ad ogni chiamata, e scarti una delle due metà. Allora il costo [tex]T[/tex] dell'algoritmo sarà [tex]T(n)=T(\frac{n}{2}) + C[/tex], dove C è il costo della chiamata a cui è aggiunto il costo della chiamata ricorsiva.
Ma [tex]T(\frac{n}{2})=T(\frac{n}{4})+C[/tex], da cui [tex]T(n)=(T(\frac{n}{4})+C) + C)=T(\frac{n}{4})+2C[/tex].
Procedendo in maniera analoga risulterà sempre che [tex]T(n)=T(\frac{n}{2^{i}})+i\cdot c[/tex]
Vogliamo fermarci alla chiamata base, di costo [tex]T(1)[/tex], che si ha quando [tex]\frac{n}{2^{i}}=1[/tex] ovvero quando [tex]i=\log_{2}n[/tex].
Sostituendo nella formula di [tex]T(n)[/tex] troviamo [tex]T(n)=T(1)+c\log_{2}n=O(\log n)[/tex], se [tex]T(1)[/tex] è costante.
Si tratta del caso più semplice, esistono pacchi di altre situazioni in cui può essere utile il Teorema Master, o ancora altri metodi di risoluzione delle relazioni di ricorrenza.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo