O(N^2) lepszyod O(N)

Podaj trzy przypadki kiedy algorytm o złożoności O(N^2) jest lepszym wyborem od algorytmu o złożoności O(N).

1. Kartkówka z programowania w liceum
2. w.w. w technikum
3. kolokwium na pierwszym roku studiów

Np.: n * n jest lepszy od n + 1000000000000 do pewnego n.

1. Złożoność pamięciowa. Można sortować liczby w O(n) ale wymaga to O(k) pamięci gdzie k to maksymalna liczba. Dla 64bitowych intów nie starczy pamieci :)
2. Stałe ukryte w notacji O, jw. sortowanie przez zliczanie niby jest O(n) ale w praktyce O(n*k), więc jak liczb jest mało a zakres liczb duzy to będzie to działać wolniej
3. Poziom skomplikowania algorytmu? Kontrowersyjne, ale w praktyce kod musi być zrozumiały :) Skomplikowany algorytm w miejscu które nie wymaga optymalizacji czasowej, może zwyczajnie nie mieć sensu, bo utrzymanie będzie kosztowne a zysk żaden.

Dodam jeszcze (pozostaje w mocy, to co napisał @Shalom), że zdanie z mojego poprzedniego postu mozna odwrócić, tzn., algorytmy są asymptotycznie lepsze, od pewnego n, co nie znaczy, że są zawsze lepsze. Ekstremalny przypadek: P = NP, ale algorytm wielomianowy jest z jakąś absurdalnie wielką stałą: n + 1000^1000(!). Wszelkie medale i wieczna chwała gwarantowane, ale praktycznie takie odkrycie zmieni nic.
Let's get real, algorytmy sortowania w bibliotekach standartowych zmieniają między implementacjami, zależnie od wielkości i rodzaju danych; algorytmy mnożenia również - np., przez dużą ilość stałych operacji, algorytm mnożenia Shonhage - Strassen, jest efektywny dopiero dla wielkich liczb.

1. Kiedy jeden jest zaimplementowany baremetal w asm a drugi w Javie.
2. Kiedy chodzi nam o ogrzanie pomieszczenia za pomocą procesora.
3. Kiedy dłuższy czas wykonywania zapewnia nam więcej czasu na opier*alanie się w pracy

Tak jak powiedział @Shalom czas wykonania to nie jedyny aspekt algorytmu, z innych (poza wymienioną złożonością pamięciową):

• cache friendliness - nawet jeśli notacja O jest lepsza dla algorytmu X, to czasem siłą zrobisz więcej niż fancy algorytmami (jeśli masz dużo siły)
• algorytm jest on-line czy off-line?
• stabilność algorytmu (czy wynik zależy od kolejności danych na wejściu)
• możliwość zrównoleglenia algorytmu oraz jaki procent pracy można zrównoleglić
• jaka jest struktura danych (ex. sortowanie niemutowalnych list przy użyciu quicksorta to średniawy pomysł)

Dodam jeszcze: kiedy algorytm O(n^2) jest znacznie prostszy oraz n jest na pewno małe lub i tak kod O(n^2) spełnia wymagania wydajnościowe, bo nie znajduje się na krytycznej ścieżce wydajnościowej. W praktyce budżet w projekcie jest ograniczony i lepiej poświęcić go na optymalizację tych fragmentów kodu, które faktycznie mają znaczenie. Jeśli w wyniku zastąpienia O(n^2) gdzieś przez O(n) czas startu aplikacji skróci się z 5 s do 4,99 s, to raczej nie ma to sensu.

No i druga sprawa, o czym pisał już Shalom - często algorytmy o niższej złożoności mają wyższą stałą. Więc dla małych n może się okazać, że O(n^2) faktycznie jest szybsze od O(n), a O(n) jest szybsze od O(1).

• kiedy deadline jest na wczoraj
• kiedy klient mało płaci
• kiedy ma działać "ch*jowo ale stabilnie"