Złożoność algorytmów sortujących

2015-02-11 22:08
0

Witam wszystkich.

Byłbym wdzięczny gdyby ktoś był w stanie wskać dwa przypadki kiedy algorytm o złożoności O(n^2) jest lepszy niż algorytm o złożoności O(n).

Lepsze od O(nlogn) jeszcze bym dał radę wskazać ale tutaj nie mam pomysłu :/

Z góry dziękuje.

Pozostało 580 znaków

2015-02-11 23:01
1

Algorytm sortujący o złożoności O(n)? Hmm, odpadają sortowania przez porównania (quicksort, heapsort, mergesort, etc). Zostają radixsorty, countsorty, bucketsorty etc

Złożoność O(n^2) ma np sortowanie przez wstawianie i działa ono bardzo szybko, gdy ilość inwersji w ciągu jest bardzo mała. Gdy jest odpowiednio mała to może być szybsze niż wymienione wcześniej liniowe algorytmy, gdyż właśnie w takich optymistycznych przypadkach złożoność insertionsorta dryfuje w stronę O(n).


"Programs must be written for people to read, and only incidentally for machines to execute." - Abelson & Sussman, SICP, preface to the first edition
"Ci, co najbardziej pragną planować życie społeczne, gdyby im na to pozwolić, staliby się w najwyższym stopniu niebezpieczni i nietolerancyjni wobec planów życiowych innych ludzi. Często, tchnącego dobrocią i oddanego jakiejś sprawie idealistę, dzieli od fanatyka tylko mały krok."
Demokracja jest fajna, dopóki wygrywa twoja ulubiona partia.

Pozostało 580 znaków

2015-02-12 00:07
1

@piter96 kwestia implementacji. Wyobraź sobie że sortujesz małą liczbę elementów z potencjalnie bardzo dużego uniwersum, np. sortujesz inty countingsortem. W przypadku naiwnego countingsorta musisz wykonać O(n+k) operacji i jeśli k >> n to nagle wcale nie jest to takie dobre. Dla int32 k jest dość spore ;) Możesz oczywiście zrobić countingsorta na treemapie, ale wtedy ryzykujesz O(logn) na każdej operacji dodawania do mapy (tree map a nie hashmap bo potrzebujemy potem wyciągać klucze w odpowiednim porządku!). W efekcie pesymistycznie masz O(nlogn + n).


Masz problem? Pisz na forum, nie do mnie. Nie masz problemów? Kup komputer...

Pozostało 580 znaków

Liczba odpowiedzi na stronę

1 użytkowników online, w tym zalogowanych: 0, gości: 1, botów: 0