Algorytmy sortowania — złożoność

Co się właśnie stało?

Sortowanie — uporządkowanie danych rosnąco lub malejąco — to jedna z najczęstszych operacji w informatyce, a o wydajności decyduje wybór algorytmu. Zwiększyliśmy liczbę elementów do 1 000 i porównaliśmy dwie strategie: proste sortowanie bąbelkowe i sprytne sortowanie przez scalanie.

Złożoność obliczeniowa (notacja „duże O")

Złożoność opisuje, jak liczba operacji rośnie z rozmiarem danych $n$. Proste algorytmy (bąbelkowe, przez wybieranie) porównują każdy element z każdym, więc wykonują ich rzędu:

Sprytne algorytmy — sortowanie przez scalanie (merge sort, opracowane przez Johna von Neumanna w 1945 r.) czy szybkie (quicksort) — dzięki strategii „dziel i zwyciężaj" (dziel dane na połowy, sortuj rekurencyjnie, scalaj posortowane części) osiągają:

Dlaczego to tak ogromna różnica?

Dla małych n różnica jest niewielka. Ale dla n = 1000 to ~1 000 000 operacji ($n^2$) kontra ~10 000 ($n\log n$) — sto razy mniej. Posortowanie miliona elementów algorytmem $O(n^2)$ wymaga bilionów operacji (godziny, a nawet dni), a $O(n\log n)$ — kilkudziesięciu milionów (ułamek sekundy). Wybór algorytmu decyduje o tym, czy program działa sekundy czy lata.

Fundament informatyki teoretycznej

Analiza złożoności pozwala przewidzieć, czy program da się w praktyce uruchomić, jeszcze zanim go napiszemy. To dlatego biblioteki standardowe (w Pythonie, Javie, C++) używają wewnątrz algorytmów rzędu $n\log n$, a nie naiwnych pętli kwadratowych.

Po co Ci to na maturze:

Sam temat złożoności leży poza podstawą programową liceum (to pogranicze matematyki i informatyki), ale logarytmy i tempo wzrostu funkcji — owszem, są. Umiejętność porównania, jak $n^2$ rośnie szybciej niż $n\log n$, to ta sama intuicja, której potrzebujesz przy zadaniach o funkcjach i ciągach.

Zapamiętaj: liczba operacji rośnie z n zgodnie ze złożonością algorytmu — bąbelkowe $\sim n^2$, scalanie $\sim n\log n$ — a różnica narasta gwałtownie wraz z rozmiarem danych. Dlatego dobór algorytmu, a nie szybszy komputer, decyduje o tym, co da się policzyć.