[Risolto][Algoritmi] calcolo tempo esecuzione funzione

[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?

[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

[jigen45]

grazie mille per la risposta ienaplinsky!!!!!

[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