Tempi di esecuzione e relazioni di ricorrenza

Fai una domanda Tutte le categorie

14 lug 2012, 09:28

Salve ragazzi avrei bisogno di risolvere il seguente esercizio, in cui si chiede prima di determinare e poi risolvere una relazione di ricorrenza.
Ecco il testo.
Considera la seguente variante di MergeSort in cui una delle due chiamate ricorsive è sostituita da una chiamata a HeapSort:

algortimo MergeHeapSort ( array A di elementi , interi i e j )
if (i m = (i+j)/2
MergeHeapSort (A,i,m)
HeapSort (A,m+1,j)
Merge (A[i,m],A[m+1,j])

Sia T(n) il tempo di esecuzione dell'algoritmo MergeHeapSort nel caso peggiore in funzione della dimensione n dell'array A .Determina e risolvi una relazione di ricorrenza per T(n).

Allora io ho risolto così ,ma avrei da chiedere alcuni chiarimenti importanti.
L'array viene diviso ogni volta in due parti uguali, su una parte
chiama ricorsivamente mergeHeapsort e sull'altra esegue heapsort..alla
fine quando si ha i>j, il merge ci mette al max O(n).
Quindi la relazione di ricorrenza dovrebbe essere T(n)=T(n/2)+ O(nlogn)
(se ij) .

Risolvendo per iterazione mi viene che

T(n/2)=T(n/4)+O(nlogn)
T(n/4)=T(n/16)+O(nlogn)
.
.
.
T[n/(2^k)]=T[n/(2^k+1)]+O(nlogn)

unendo tutto si ottiene T(n)=T(n/2^k)+k*O(nlogn) -->
T(n)=T(n/2^k)+O(k*nlogn) (perchè si può portare dentro all' O(..) la
costante moltiplicativa)

Alla fine mi fermo per (n/(2^k)) = 1--> k=log(n) (in base 2)

sostituisco k e ottengo T(n)=T(1)+O(n(logn)^2)---> T(n)=O(n*log^2(n))

Quello che non capisco sulla relazione di ricorrenza, che dovrebbe essere giusta a quanto pare detto dal professore, è il secondo pezzo per i>j. Io all'inizio avrei messo i tempi delle tre funzioni tutte in un'unica relazione di ricorrenza