Complessità cancellazione Binary Tree

[Slashino1]

La formula ricorsiva da risolvere è la seguente :


$T(n)={(c_1,if n=1),(T(n/2)+O(log(n)),if n>1):}$. L'unico metodo che ci è stato spiegato è quello iterativo, che mi da come risultato: $ T(n)= T(n/2^k) + O\sum_{n=0}^(k-1) log(n/2^i) $ ma non so come calcolare la somma della serie :S Qualcuno è in grado di aiutarmi?
ps: L'algoritmo è questo http://www.ateneonline.it/foggiavento/l ... ecursive.c e quel $ Olog(n) $ viene fuori in seguito alla chiamata di search_min.

[hamming_burst]

"Slashino":La formula ricorsiva da risolvere è la seguente :


$T(n)={(c_1,if n=1),(T(n/2)+O(log(n)),if n>1):}$. L'unico metodo che ci è stato spiegato è quello iterativo, che mi da come risultato: $ T(n)= T(n/2^k) + O\sum_{n=0}^(k-1) log(n/2^i) $ ma non so come calcolare la somma della serie :S Qualcuno è in grado di aiutarmi?
ps: L'algoritmo è questo http://www.ateneonline.it/foggiavento/l ... ecursive.c e quel $ Olog(n) $ viene fuori in seguito alla chiamata di search_min.

attenzione agli indici, $i$ è il valore che si itera e $k$ sarà $log_2(n)$ e il $log()$ della sommatoria lo consideriamo anche quello in base $2$ così per semplicità.
basta usare semplici proprietà dei logaritmi e delle sommatorie.
$\sum_{i=0}^(log_2(n)-1) log_2(n/2^i) = \sum_{i=0}^(log_2(n)-1) (log_2(n) - log_2(2^i)) = $
$= (log_2(n)-1)log_2(n) - \sum_{i=0}^(log_2(n)-1) i =$
$= log_2^2(n)-log_2(n) - {(log_2(n)-1)((log_2(n)-1)+1)}/2 =$
$= log_2^2(n) - log_2(n) - 1/2log_2^2(n)-1/2log_2(n) in O(log_2^2(n))$ che in generale vale $O(log(n))$ cioè base generica.

[Slashino1]

...a parte la questione degli indici che ho sbagliato a trascrivere, anche io avevo operato così ma vedendo quel logaritmo al quadrato ero convinto di aver sbagliato qualcosa. Ciò che non mi è chiaro è questo:

"hamming_burst":... che in generale vale $O(log(n))$ cioè base generica.

...dire che $T(n) in O(log^2n) $ mica implica che $T(n) in O(log(n)) $ ?

[hamming_burst]

"Slashino":Ciò che non mi è chiaro è questo:
[quote="hamming_burst"]... che in generale vale $O(log(n))$ cioè base generica.

...dire che $T(n) in O(log^2n) $ mica implica che $T(n) in O(log(n)) $ ?[/quote]
Certo certo, se ragioniamo per ordini di grandezza hai ragione.

Ma se guardi l'esatto calcolo noti che ci sono delle sottrazione e ciò "giustifica" empiricamente tale complessità.
Comunque se sui libri si inizia a scrivere la complessità esatta, tenendo conto della base e delle potenze non si finisce più. Per questo con la forma $O(log(n))$ si intende dire che ha complessità di classe logaritmica (un insieme che contiene tutte le basi, tutte le potenze), se la potenza fosse elevata allora avrebbe senso, ma per un quadrato poco cambia all'acuratezza del significato.

[Slashino1]

Ok, adesso mi è tutto chiaro allora. Grazie mille