Complessità Algoritmi Ricorsivi
Allora mi serve un metodo per calcolare la complessità $T(n)$ di un algoritmo ricorsivo; ovvero dato un qualsiasi algoritmo ricorsivo dovrei riuscire a identificare un $T(alpha)$ che rappresenta il caso base della ricorsione e un $T(n)$ e poi stimare la complessità (limite superiore) O-grande.
Risposte
Si tratta di un argomento abbastanza vasto ed esistono numerose tecniche per calcolare la complessità di un algoritmo ricorsivo. Sei interessato a qualche problema più specifico?
Questo è uno degli esempi delle dispense, sapete dirmi che metodo è?
int fact(int n)
{
if (n≤1) return 1; /* Caso Base */
return n*fact(n-1); /* Passo Induttivo */
}
$T(n)= { ( O(1) se n=1 ),( O(1)+T(n-1) se n>1 ):} $
Equazione di ricorrenza
Base: $T(1) = a$
Induzione: $T(m) = b + T(m-1)$
Caso Base: $T(0) = O(1)$
$T(1) = O(1)$
Passo Induttivo: $O(1) + max(O(1), T(n-1))$
$O(1) + T(n-1)$ per $n>1$
Per il fattorale, l’analisi risulta $T(n) = O(n)$
int fact(int n)
{
if (n≤1) return 1; /* Caso Base */
return n*fact(n-1); /* Passo Induttivo */
}
$T(n)= { ( O(1) se n=1 ),( O(1)+T(n-1) se n>1 ):} $
Equazione di ricorrenza
Base: $T(1) = a$
Induzione: $T(m) = b + T(m-1)$
Caso Base: $T(0) = O(1)$
$T(1) = O(1)$
Passo Induttivo: $O(1) + max(O(1), T(n-1))$
$O(1) + T(n-1)$ per $n>1$
Per il fattorale, l’analisi risulta $T(n) = O(n)$
Ciao,
a me sembra hai posto due domande:
- quale è il metodo per trasformare un algoritmo ricorsivo in una formula chiusa (le equazioni ricorsive) o analizzare il suo costo
- come calcolare un'equazione ricorsiva e valutarla in una classe di complessità.
Questi metodi vanno sotto il nome di Analisi degli Algoritmi, e sono composti da varie tecniche di calcolo e dimostrazione (come ti è stato fatto notare è un argomento vasto, se ha un suo nome proprio
).
Esempio il tuo utilizza il più classico dei classici: dimostrazione per induzione anche se manca di tutto (nell'algoritmica si chiama "metodo di sostituzione" o "metodo per tentativi".
Se hai bisogno di esempi di:
- calcolo costi degli algoritmi
- calcolo di un'equazione di ricorrenza
vedi qui.
Se hai problemi basta sempre postare (consiglio: non essere così sintetico nello scrivere, non possiamo noi capire quale è il tuo problema se non ci dici il dubbio)
a me sembra hai posto due domande:
- quale è il metodo per trasformare un algoritmo ricorsivo in una formula chiusa (le equazioni ricorsive) o analizzare il suo costo
- come calcolare un'equazione ricorsiva e valutarla in una classe di complessità.
Questi metodi vanno sotto il nome di Analisi degli Algoritmi, e sono composti da varie tecniche di calcolo e dimostrazione (come ti è stato fatto notare è un argomento vasto, se ha un suo nome proprio
).Esempio il tuo utilizza il più classico dei classici: dimostrazione per induzione anche se manca di tutto (nell'algoritmica si chiama "metodo di sostituzione" o "metodo per tentativi".
Se hai bisogno di esempi di:
- calcolo costi degli algoritmi
- calcolo di un'equazione di ricorrenza
vedi qui.
Se hai problemi basta sempre postare (consiglio: non essere così sintetico nello scrivere, non possiamo noi capire quale è il tuo problema se non ci dici il dubbio)
Il metodo che stai utilizzando si basa sul risolvere un sistema composto da un elemento chiamato base ed da uno chiamato induzione... si basa sul metodo delle sostituzioni successive conoscendo a priori come evolve il numero di elementi da una ricorsione alla successiva, può risultare molto utile nel calcolo della complessità computazione in alberi binari ma spesso risulta inutilizzabile per altri algoritmi, esistono dei teoremi che ti permettono di conoscere immediatamente la complessità computazione.
Es ricerca in un albero binario di ricerca per ipotesi bilanciato.
${(0(1)),(T(n)=0(1)+T(n/2)):}$
La base indica la complessità quando non hai più ritorsione.
L'induzione è la complessità durante la ricorsione(in questo caso il numero di elementi si dimezza da una ricorsione all'altra)
Es ricerca in un albero binario di ricerca per ipotesi bilanciato.
${(0(1)),(T(n)=0(1)+T(n/2)):}$
La base indica la complessità quando non hai più ritorsione.
L'induzione è la complessità durante la ricorsione(in questo caso il numero di elementi si dimezza da una ricorsione all'altra)
Teorema fondamentale delle ricorrenze
Dato:
$T(x)={(a T(n/b)+f(n) con (n>1) ),(O(1) con (n=1)):}$
Seguono due eventualità:
1)
se
$f(n)$ è $0(n^(log_b(a-\epsilon))) con \epsilon>0$
$T(n)$ è $O(n^(log_b(a)))$
2)
se
$f(n)$ è $O(n^(log_b(a)))$
$T(n)$ è $O(n^(log_ba*logn))$
nota quindi la complessità della funzione f(n) che puoi facilmente calcolare con i teoremi di base:
Non so se sei a conoscenza, ti elenco ugualmente qualche proprietà:
-Ricorda che ogni istruzione elementare ha complessità 0(1)
-Teorema della somma: 0(1)+0(1)=0(1)
ha complessità $O(1)*n=O(n)$
e soprattutto ricorda sempre di considerare il caso peggiore!
Dato:
$T(x)={(a T(n/b)+f(n) con (n>1) ),(O(1) con (n=1)):}$
Seguono due eventualità:
1)
se
$f(n)$ è $0(n^(log_b(a-\epsilon))) con \epsilon>0$
$T(n)$ è $O(n^(log_b(a)))$
2)
se
$f(n)$ è $O(n^(log_b(a)))$
$T(n)$ è $O(n^(log_ba*logn))$
nota quindi la complessità della funzione f(n) che puoi facilmente calcolare con i teoremi di base:
Non so se sei a conoscenza, ti elenco ugualmente qualche proprietà:
-Ricorda che ogni istruzione elementare ha complessità 0(1)
-Teorema della somma: 0(1)+0(1)=0(1)
for(i=0;i<n;i++)
printf("ciao");
ha complessità $O(1)*n=O(n)$
e soprattutto ricorda sempre di considerare il caso peggiore!
"nunziox":
Teorema fondamentale delle ricorrenze
Dato:
$T(x)={(a T(n/b)+f(n) con (n>1) ),(O(1) con (n=1)):}$
Il Master Theorem è molto comodo in ricorrenze del tipo che hai mostrato, ma attenzione ha citare e formalizzare bene i casi (sono 3).
Non sovrapporre le notazioni $Theta()$ con $O()$ come fanno certi libri o autori, c'è una bella differenza.
"nunziox":
1)
se
$f(n)$ è $0(n^(log_b(a-\epsilon))) con \epsilon>0$
$T(n)$ è $O(n^(log_b(a)))$
meglio:
$f(n)$ è $O(n^(log_b(a)-\epsilon))\ con\ \epsilon>0$
$T(n)$ è $\Theta(n^(log_b(a)))$
2)
se
$f(n)$ è $O(n^(log_b(a)))$
$T(n)$ è $O(n^(log_b(a*logn)))$
meglio:
$f(n)$ è $Theta(n^(log_b(a)))$
$T(n)$ è $Theta(n^(log_b(a))*logn)$
caso 3: cito solo la formulazione (ci sono dei sottocasi per la validità, basta anche wiki per saperli):
$f(n)$ è $\Omega(n^(log_b(a)+\epsilon))$
$T(n)$ è $\Theta(f(n))$
Grazie:) il mio prof a lezione lo ha citato senza distinguere le due notazioni. Grazie per la correzione. 
"nunziox":
Grazie:) il mio prof a lezione lo ha citato senza distinguere le due notazioni. Grazie per la correzione.
Prego
Diciamo che informalmente e in pratica si utilizzano solo 2 casi e la notazione O-grande come hai scritto (o detto il docente). Il Master Theorem è molto utile per dare un'idea della complessità di una tal ricorrenza e per la sua praticità.
Alle volte non iteressa molto che sia $Theta()$ $O()$ ecc... ma si cerca una stima veloce e ad occhio, per qusto non interessa il formalismo.
Ma finchè si studa in università meglio essere formali, poi si può livellare le cose inutili quanto vuoi (ma bisogna sapere cosa è corretto e cosa no)
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo