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.