Pokaż, że czas działania algorytmu heapsort wynosi...
Pokaż, że czas działania algorytmu heapsort wynosi...
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 ?
-
- Użytkownik
- Posty: 2000
- Rejestracja: 19 lut 2008, o 17:35
- Płeć: Mężczyzna
- Lokalizacja: Stare Pole/Kraków
- Podziękował: 60 razy
- Pomógł: 202 razy
Pokaż, że czas działania algorytmu heapsort wynosi...
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()}\)
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()}\)