Algorytm magicznych piątek: Różnice pomiędzy wersjami
| [wersja przejrzana] | [wersja przejrzana] |
Usunięta treść Dodana treść
AndrzeiBOT (dyskusja | edycje) m Drobne redakcyjne - poprawki linków, apostrofów, cudzysłowów... |
|||
Linia 15:
* znajdowania median piątek, wykonywanego w czasie <math>\Theta(n)\!</math>
* wybierania (rekurencyjnie) mediany zbioru <math>A_5</math>, wykonywanego w czasie <math>T\left(\frac{n}{5}\right)</math>
* wykonania wywołania rekurencyjnego, wykonywanego co najwyżej w czasie <math>T(\max(|A_<|,|A_>|))\!</math>
Jak wcześniej zauważyliśmy <math>\max(|A_<|,|A_>|)\leqslant\frac{3n}{4}</math>, zatem szacując czas wykonania całego algorytmu przez sumę maksymalnych czasów wykonań kroków dostajemy nierówność
: <math>T(n)\leqslant\Theta(n)+T\left(\frac{n}{5}\right)+T\left(\frac{3n}{4}\right)</math>.
Stosując standardowe metody rozwiązywania nierówności asymptotycznych (kluczowe jest, że <math>\frac{1}{5}+\frac{3}{4}=\frac{19}{20}<1</math>) dostajemy, że algorytm magicznych piątek nawet pesymistycznie jest liniowy.
| |||