Heapsort Sortowanie przez kopcowanie

[mafia2802]

Mam nastepujaca funkcje w pseudokodzie:

Kod: Zaznacz cały

CONSTRUCTHEAP(A,r,n)

1 if(r<=(n/2))
2 then CONSTRUCTHEAP(A,2*r,n)
3 CONSTRUCTHEAP(A, 2*r+1,n)
4 FIXHEAP(A,n,r)

zastanawiam sie jaka jest zlozonosc obliczeniowa tej funkcji, myslalem o nstepujacej rekurencji
T(n)=2*T(n/2) + c * lgn, c- stala, oraz T(1)=0,
tylko nie wiem jak to udowodnic zarowno ta zlozonosc jak i ta rekurencje

Za pomoc z gory dziekuje[/code]

[Dumel]

tak to zapisałeś że za bardzo nie wiadomo co jest czym, ale pokolei:
HEAPSORT:
1. budowanie kopca - O(n)
2. n iteracji: zdejmnij element kopca na 1. pozycji, wstaw w jego miejsce ostatni element, przywróć własności kopca - całość O(nlgn)

czyli złożność algorytmu wynosi O(nlgn)