Pagina 1 di 1
[Risolto][Algoritmi] calcolo tempo esecuzione funzione
Inviato: venerdì 6 giugno 2014, 22:43
da jigen45
Ragazzi, supponendo che la funzione test(x) abbia tempo di esecuzione O(xlgx), devo calcolare il tempo della funzione fun
Codice: Seleziona tutto
fun(intero n)
i = 1
while i <= n do
test(i)
i = i * 2
ora il ciclo viene eseguito O(lgn) volte, test(i) O(i*lg(i)) ho maggiorato quest'ultimo con O(nlgn) quindi come tempo totale F(n) ho O(nlgn*lgn) però non mi sembra scritta bene.. che ne dite?
Re: [Algoritmi] calcolo tempo esecuzione funzione
Inviato: lunedì 9 giugno 2014, 19:42
da ienaplinsky
no no fai attenzione che il risultato è sbagliato
l algoritmo impiega questo tempo:
sommatoria per i da 1 a log n di 2^i * log 2^i = sommatoria per i da 1 a log n di 2^i * i che al momento non ricordo come si risolve xd
se mi viene in mente te lo posto
Re: [Algoritmi] calcolo tempo esecuzione funzione
Inviato: lunedì 9 giugno 2014, 22:24
da jigen45
grazie mille per la risposta ienaplinsky!!!!!
Re: [Algoritmi] calcolo tempo esecuzione funzione
Inviato: lunedì 9 giugno 2014, 22:47
da ienaplinsky
aspetta che ho trovato la soluzione ringraziamo google xd
https://answers.yahoo.com/question/inde ... 252AA3Y4kh
stando a quello che si dice qua (e mi sembra esatto anche se le serie geometriche non le tocco da parecchio) la sommatoria è uguale a
(log n - 1) * 2 ^(log n + 1) + 2 che facendo i conti è = a 2 n log n - 2 n + 2 e si può dimostrare che è un O(nlogn)
considerando che il log è in base 2