Pokaż, że czas działania algorytmu heapsort wynosi...

[Oslo]

Pokaż, że czas działania algorytmu heapsort wynosi Ω(n lg n). Jak w temacie mam otrzymać to równanie i dokładnie opisać skąd się co wzięło... pomożecie ?

[Dumel]

na wiki masz ładną animację obrazującą działanie algorytmu: ... kopcowanie
zakładam ze wiesz na czym polega algorytm. w czasie tworzenia kopca stale utrzymuje się jego wysokość \(\displaystyle{ O(logk)}\) po dodaniu k elementow więc ta czesc zajmuje nie wiecej niz \(\displaystyle{ O(log1)+O(log2)+...+O(logn)=O(nlogn)}\)
samo sortowanie zajmuje czas (kozystam ze wzoru Stirlinga) \(\displaystyle{ \Omega(log1)+\Omega(log2)+...+\Omega(logn)=\Omega(log(n!))=\Omega (log( (\frac{n}{e})^n \sqrt{2 \pi n}))=\Omega(nlogn)}\)

[edit]to jest zle, ten wzor Stirlinga jest nipotrzebny a to wyprowadzenie jest prawidłowe tylko dla notacji \(\displaystyle{ O()}\)