Esercizio Tempo di esecuzione di funzioni (in pseudocodice)

[Andrew Ryan]

Siccome non ho molta dimestichezza con l'analisi asintotica di algoritmi,ho fatto un esercizio ma sono dubbioso sulle soluzioni:

Ho queste due funzioni in pseudocodice

fun1(int k) {
if k<=1 then return;
fun1(k/3);
fun1(k/3);
}


fun2(int n){
i=1
while(i fun1(i)
i = 2^i
}
}

Domanda n°1: Qual'è il tempo di esecuzione di fun1 in funzione di k?

Ho risposto Theta-grande( log n)

Domanda n°2: Qual'è il tempo di esecuzione di fun2 in funzione di n?

Ho risposto Theta-grande(2^n log n)

Ho risposto correttamente?

P.S: i log sono da considerarsi in base 2

[hamming_burst]

fun1: $2T(k/3) + c\ \in^?\ O(log_2(k))$ ($\Theta(log_2(n))$ lasciamolo da parte per semplicità)

Ho risposto correttamente?

abbiamo una limitazione e la sua ricorrenza, dimostriamolo allora:

$2T(k/3) + c <= 2d*log_2(k/3) + c <= 2d(log_2(k) - log_2(3)) + c <= 2d*log_2(k) - 2d*log_2(3) + c$
\[2d*log_2(k) - 2d*log_2(3) + c \nleq d*log_2(k)\] per nessun $d>0$

perciò, prova a ricalcolare la ricorrenza.

fun2 è iterativa perciò non ha una "ricorrenza" nel vero senso del termine, ma si può calcolare direttamente la limiazione in funzione di fun1:

$2^i < n$ è "limitato" dal logartimo $i < log_2(n)$

perciò la complessità dicendo che $fun1(i) in O(f(log_2(n)))$ allora è un'iterazione e si moltiplica.

$fun2 \in O(log_2(n)*f(log_2(n)))$

sistema la ricorrenza di fun1 ricalcolandola.

PS: perchè scrivi Theta-grande? C'è anche Theta-piccolo? (in lettere greche sì, ma diversificazione no).

[Andrew Ryan]

"hamming_burst":fun1: $2T(k/3) + c\ \in^?\ O(log_2(k))$ ($\Theta(log_2(n))$ lasciamolo da parte per semplicità)

Ho risposto correttamente?

abbiamo una limitazione e la sua ricorrenza, dimostriamolo allora:

$2T(k/3) + c <= 2d*log_2(k/3) + c <= 2d(log_2(k) - log_2(3)) + c <= 2d*log_2(k) - 2d*log_2(3) + c$
\[2d*log_2(k) - 2d*log_2(3) + c \nleq d*log_2(k)\] per nessun $d>0$

perciò, prova a ricalcolare la ricorrenza.

fun2 è iterativa perciò non ha una "ricorrenza" nel vero senso del termine, ma si può calcolare direttamente la limiazione in funzione di fun1:

$2^i < n$ è "limitato" dal logartimo $i < log_2(n)$

perciò la complessità dicendo che $fun1(i) in O(f(log_2(n)))$ allora è un'iterazione e si moltiplica.

$fun2 \in O(log_2(n)*f(log_2(n)))$

sistema la ricorrenza di fun1 ricalcolandola.

PS: perchè scrivi Theta-grande? C'è anche Theta-piccolo? (in lettere greche sì, ma diversificazione no).

non abbiamo visto l'analisi asintotica in maniera così approfondita,le notazioni asintotiche usate nel mio corso sono soltanto 3,O-grande per il caso peggiore (limite superiore),Omega-grande per il caso migliore (limite inferiore),Theta-grande per caso medio (limite stretto)

[hamming_burst]

"Andrew Ryan":non abbiamo visto l'analisi asintotica in maniera così approfondita,

come hai calcolato la complessità di fun1? perchè proprio $\Theta(log_2(k))$?

le notazioni asintotiche usate nel mio corso sono soltanto 3,O-grande per il caso peggiore (limite superiore),Omega-grande per il caso migliore (limite inferiore),Theta-grande per caso medio (limite stretto)

sono quelle che si utilizzano di solito...
Volevo solo farti notare che non esiste Theta-piccolo, perciò diversificare da Theta-grande non ha molto senso. Danno la stessa informazione.

[Andrew Ryan]

Ricalcolando la ricorrenza di fun1 è possibile che sia O(log n/3) ?

Quanto alla notazione,avevo letto male,ho specificato Theta-grande per il modo in cui è scritta,alla fine come dici tu potevo anche omettere il "grande"

[hamming_burst]

"Andrew Ryan":Ricalcolando la ricorrenza di fun1 è possibile che sia O(log n/3) ?

ok, mi proponi un'altra complessità. Ma quello che ti chiedo che metodo di calcolo utilizzi. Come fai a dare una complessità a quell'algoritmo?

es. esiste il metodo dell'albero, della sostituzione, Master Theorem (ovviamente tutti per le ricorrenze)....

[Andrew Ryan]

"hamming_burst":[quote="Andrew Ryan"]Ricalcolando la ricorrenza di fun1 è possibile che sia O(log n/3) ?

ok, mi proponi un'altra complessità. Ma quello che ti chiedo che metodo di calcolo utilizzi. Come fai a dare una complessità a quell'algoritmo?

es. esiste il metodo dell'albero, della sostituzione, Master Theorem (ovviamente tutti per le ricorrenze)....[/quote]Diciamo che queste ricorrenze non sono riuscito a capirle molto bene e quella complessità l'ho ipotizzata senza seguire un metodo

ora,seguendo questo pdf:http://tinyurl.com/7qj4g2k e guardando il metodo dell'albero di ricorsione che mi è sembrato quello un po' più semplice,sono giunto alla conclusione che la complessità di fun1 corrisponde a $ \Theta (k/3^n log(n) )$,è corretto?

P.S: il log è in base 2

[hamming_burst]

proviamo a calarlo con l'albero allora...

c $T(n)$ -> c c $T(n/3)$ = $2c$ -> c c c c $T((n/3)/3)$ = $2*2c$ -> .... -> $(2^i)*c T(n/3^i)$ ... -> finchè $n/3^i = 1$ cioè quando $i=log_3(n)$

perciò la complessità è la somma dei vari rami: $sum_{i=0}^{log_3(n)-1}2^i*c = c*(2^{log_3(n)} - 1)/(2-1) \in O(n^{log_3(2)})$
le foglie sono: $O(n^{log_3(2)})$

perciò la complessità risultante dell'algoritmo è $O(n^{log_3(2)})$

se non comprendi qualcosa ne riparliamo...

[Andrew Ryan]

"hamming_burst":proviamo a calarlo con l'albero allora...

c $T(n)$ -> c c $T(n/3)$ = $2c$ -> c c c c $T((n/3)/3)$ = $2*2c$ -> .... -> $(2^i)*c T(n/3^i)$ ... -> finchè $n/3^i = 1$ cioè quando $i=log_3(n)$

perciò la complessità è la somma dei vari rami: $sum_{i=0}^{log_3(n)-1}2^i*c = c*(2^{log_3(n)} - 1)/(2-1) \in O(n^{log_3(2)})$
le foglie sono: $O(n^{log_3(2)})$

perciò la complessità risultante dell'algoritmo è $O(n^{log_3(2)})$

se non comprendi qualcosa ne riparliamo...

non ho capito perchè la sommatoria è diventata $ c*(2^{log_3(n)} - 1)/(2-1) $ ma probabilmente avrai applicato una regolare che ora mi sfugge

[hamming_burst]

è semplicemente la formula chiusa della serie geometrica troncata

[Andrew Ryan]

perchè alla fine viene scelto $ n^{log_3(2)} $ come elemento dominante?

inoltre,il metodo dell'albero di ricorsione può essere utilizzato per calcolare qualsiasi ricorrenza? Grazie

EDIT:

in conclusione,la complessità di fun2 è $ O(n^{log_3(2)} * log_2(n)) $ ?

[hamming_burst]

"Andrew Ryan":perchè alla fine viene scelto $ n^{log_3(2)} $ come elemento dominante?

ti sembra ci siano altri possibili casi che lo sovrastano? Mi pare ci sia al massimo un termine $c$ costante (e un altro piccolo termine costante che evito di scriverti..).

inoltre,il metodo dell'albero di ricorsione può essere utilizzato per calcolare qualsiasi ricorrenza? Grazie

dipende dal tipo di ricorrenza. Anche se è un metodo semplice da visualizzare, ci sono casi che produce dei calcoli piuttosto complessi ed incriccati. Es. un po' estremo per farti capire di cosa parlo: ricorrenza-t81907.html
Diciamo che funziona quasi con tutte le più diffuse ricorrenze, a patto di sorbirsi lunghi calcoli.

Ma ci sono casi che rende tutto molto semplice per chi cerca di risolverle. Se vuoi degli esempi prova a cercare nella sezione ne abbiamo risolte a quintali ed in tutti i modi. Ovviamente siam qui sei hai bisogno di chiarimenti.

EDIT:

in conclusione,la complessità di fun2 è $ O(n^{log_3(2)} * log_2(n)) $ ?

no.
Io ho parlato di $O(f(log_2(n)))$ perciò devi sostituire $n$ con $log_2(n)$. Quindi: $O(log_2^{log_3(2)}(n)* log_2(n)) $

Per farla semplice puoi notatre che $log_2^{log_3(2)}(n) \approx log_2(n)$ perciò la tua complessità è sovrastata da $O(log_2^2(n))$. Ma quella che abbiam calcolato è molto più precisa e stretta, dire che ci calza perfettamente

Se vuoi per completare puoi dimostrare per induzione che ciò che abbiam calcolato è corretto.

[Andrew Ryan]

"hamming_burst":[quote="Andrew Ryan"]perchè alla fine viene scelto $ n^{log_3(2)} $ come elemento dominante?

ti sembra ci siano altri possibili casi che lo sovrastano? Mi pare ci sia al massimo un termine $c$ costante (e un altro piccolo termine costante che evito di scriverti..).
[/quote]mi scuso per l'insistenza ma non mi è ancora chiaro il modo in cui viene scelto $ n^{log_3(2)} $ come elemento dominante,nel calcolo della serie c'era $ 2^{log_3(n)} $,perchè nell'elemento dominante il 2 e n si sono scambiati di posto? hai seguito un calcolo o lo dici a occhio ?

[hamming_burst]

"Andrew Ryan":[quote="hamming_burst"][quote="Andrew Ryan"]perchè alla fine viene scelto $ n^{log_3(2)} $ come elemento dominante?

ti sembra ci siano altri possibili casi che lo sovrastano? Mi pare ci sia al massimo un termine $c$ costante (e un altro piccolo termine costante che evito di scriverti..).
[/quote]mi scuso per l'insistenza ma non mi è ancora chiaro il modo in cui viene scelto $ n^{log_3(2)} $ come elemento dominante,nel calcolo della serie c'era $ 2^{log_3(n)} $,perchè nell'elemento dominante il 2 e n si sono scambiati di posto? hai seguito un calcolo o lo dici a occhio ? [/quote]
ah in questo senso non capivi...pensavo in senso algoritmico e complessità.
Quella è una semplice equivalenza algebrica, utilizzando le proprietà dell'esponenziale in base qualunque.

\[a^{\log_{b}(n)} = n^{\log_{b}(a)}\]

[Andrew Ryan]

"hamming_burst":
ah in questo senso non capivi...pensavo in senso algoritmico e complessità.
Quella è una semplice equivalenza algebrica, utilizzando le proprietà dell'esponenziale in base qualunque.

\[a^{\log_{b}(n)} = n^{\log_{b}(a)}\]

ok,a questo punto sembra essere tutto chiaro,ti ringrazio davvero