Cześć
Jak wiadomo, ograniczenie dolne na sortowanie to \(\displaystyle{ O(n \log n).}\) Wiadomo, że istnieją sortownia w czasie liniowym ( CountSort , RadixSort), ale one zakładają przypadek szczególny.
Stąd też wynika pytanie, skąd wynika dolne ograniczenie na sortowanie?
[Algorytmy] Sortowanie przez porównania kluczy, ograniczenie
- Dasio11
- Moderator
- Posty: 10225
- Rejestracja: 21 kwie 2009, o 19:04
- Płeć: Mężczyzna
- Lokalizacja: Wrocław
- Podziękował: 40 razy
- Pomógł: 2362 razy
[Algorytmy] Sortowanie przez porównania kluczy, ograniczenie
W dowodzie, jaki znam, zakłada się, że algorytm podejmuje decyzje tylko na podstawie porównań liniowych kombinacji danych. Następnie pokazuje się, że algorytm, który zawsze wykonuje mniej niż \(\displaystyle{ \Theta( n \log n )}\) porównań, nie może zawsze zwracać poprawnego wyniku.