Pami臋tacie wpis o dziwnych algorytmach sortuj膮cych?
Nie pami臋tacie?
No przecie偶 tu jest: http://xpil.eu/yyc
Na pocz膮tku wymieniam tam QuickSort jako najszybszy znany wsp贸艂cze艣nie algorytm do sortowania danych.
Istotnie, na dzie艅 dzisiejszy nie uda艂o si臋 skonstruowa膰 niczego szybszego od QuickSort. Od lat jest to czempion w艣r贸d algorytm贸w, wraz z HeapSort oraz MergeSort, kt贸re s膮 troch臋 wolniejsze, ale nie za wiele.
No i teraz ciekawostka: ilo艣膰 operacji, kt贸re algorytm QuickSort musi wykona膰, aby posortowa膰 list臋 n-elementow膮, jest w przybli偶eniu r贸wna n-tej z kolei liczbie pierwszej przemno偶onej przez 10!
(wykrzyknik powy偶ej oznacza zaskoczenie, nie silni臋...)
Jeszcze raz:
Bierzemy list臋, dajmy na to, 200-elementow膮.
Sortujemy j膮 za pomoc膮 QuickSort, licz膮c w czasie sortowania ile operacji algorytm wykonuje (operacje czyli odczyt, zapis, zamiana element贸w, por贸wnanie warto艣ci i tak dalej).
Powtarzamy to samo dla innej listy.
I dla jeszcze innej.
I jeszcze raz.
Powtarzamy sortowanie dwustu element贸w na r贸偶nych listach tak d艂ugo, a偶 b臋dziemy mieli do艣膰, a potem jeszcze drugie tyle. Za ka偶dym razem liczymy ilo艣膰 operacji, kt贸re QuickSort musia艂 wykona膰, 偶eby uko艅czy膰 sortowanie.
Na koniec liczymy 艣redni膮 z tych wszystkuch sortowa艅.
Oka偶e si臋, 偶e nasz licznik operacji dobija (艣rednio) do 12018. A dwusetna z kolei liczba pierwsza to 1223, co przemno偶one przez 10 daje 12230, czyli nieca艂e 2% b艂臋du.
Przy wi臋kszych (d艂u偶szych) listach b艂膮d maleje.
Dla listy 2000-elementowej 艣rednia ilo艣膰 operacji to 173925, a dwutysi臋czna z kolei liczba pierwsza to 17389, co przemno偶one przez 10 daje 173890 (czyli b艂膮d w okolicach 0.02%)
Czy mamy tu do czynienia z magi膮?
Nie. Zjawisko to ma bardzo konkretne matematyczne wyja艣nienie. Ot贸偶 jak powszechnie wiadomo liczby pierwsze podlegaj膮 Twierdzeniu O Liczbach Piewszych, kt贸re m贸wi, 偶e n-ta z kolei liczba pierwsza jest w przybli偶eniu r贸wna n*log(n).
Z kolei z艂o偶ono艣膰 obliczeniowa algorytmu QuickSort wynosi O(n log(n)).
Jak wida膰 jest tu bezpo艣rednia zale偶no艣膰, chocia偶 ma艂o kto o niej wie 馃槈
Je偶eli chcesz do komentarza wstawi膰 kod, u偶yj sk艂adni:
[code]
tutaj wstaw sw贸j kod
[/code]
Je偶eli zrobisz liter贸wk臋 lub zmienisz zdanie, mo偶esz edytowa膰 komentarz po jego zatwierdzeniu.