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.
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).
@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).