Złożoność O(n log n) bez tajemnic - sortowanie i rekurencja

Gdy program zaczyna przetwarzać tysiące lub miliony elementów, samo „działa” przestaje wystarczać. Właśnie wtedy złożoność O(n log n) staje się ważnym punktem odniesienia, bo opisuje algorytmy wyraźnie szybsze od kwadratowych, a jednocześnie wystarczająco uniwersalne do pracy z dużymi zbiorami danych. Pokażę, skąd bierze się ten wynik, gdzie spotkasz go w kodzie i jak nie pomylić dobrej klasy z gwarancją konkretnego czasu wykonania.

Co naprawdę oznacza złożoność liniowo-logarytmiczna

Litera n oznacza rozmiar danych wejściowych, na przykład liczbę elementów tablicy. Logarytm opisuje liczbę etapów, w których problem zmniejsza się wielokrotnie, zwykle przez podział na połowy. Iloczyn tych dwóch wartości mówi, że algorytm wykonuje pracę liniową w każdym z około logarytmicznych poziomów.

Dobrym przykładem jest sortowanie przez scalanie. Tablica zostaje podzielona na coraz mniejsze fragmenty, aż pozostaną pojedyncze elementy. Później fragmenty są scalane w uporządkowany sposób. Na każdym poziomie trzeba przejrzeć łącznie około n elementów, a liczba poziomów wynosi mniej więcej log₂ n.

Dlaczego podstawa logarytmu zwykle nie zmienia wyniku

W analizie asymptotycznej logarytm o podstawie 2, 10 czy e różni się tylko stałym mnożnikiem. Dlatego zapis z różnymi podstawami nadal należy do tej samej klasy wzrostu. W realnym programie stały mnożnik może mieć znaczenie, ale przy porównywaniu klas najważniejszy jest sposób, w jaki koszt rośnie wraz z n.

Dla przykładu, gdy mamy 1024 elementy, podział na połowy daje 10 poziomów, ponieważ 2¹⁰ = 1024. Przy milionie elementów jest ich około 20. To właśnie sprawia, że dodatkowy czynnik logarytmiczny rośnie stosunkowo wolno.

Gdzie najczęściej pojawia się ten wynik

Najbardziej znanym zastosowaniem jest sortowanie. Algorytmy oparte na porównywaniu elementów nie mogą w ogólnym przypadku sortować dowolnych danych szybciej niż w granicy Ω(n log n). Nie oznacza to, że każdy problem sortowania musi mieć taki koszt, ponieważ specjalne dane, ograniczony zakres wartości lub dodatkowe założenia mogą pozwolić użyć metod liniowych.

Sortowanie przez scalanie

Merge sort ma czas działania rzędu O(n log n) w najlepszym, średnim i najgorszym przypadku. To jego największa zaleta, szczególnie gdy przewidywalność jest ważniejsza niż minimalne zużycie pamięci. Wadą pozostaje zwykle dodatkowa pamięć potrzebna do scalania fragmentów.

W praktyce sięgam po tę metodę wtedy, gdy potrzebuję stabilnego sortowania. Stabilność oznacza, że elementy o równych kluczach zachowują wcześniejszą kolejność, co ma znaczenie na przykład przy sortowaniu rekordów najpierw po nazwisku, a potem po dacie.

Quicksort

Quicksort działa średnio w klasie O(n log n), ale przy niekorzystnym wyborze elementu rozdzielającego może zejść do O(n²). Dlatego współczesne implementacje stosują strategie ograniczające ryzyko złego podziału, takie jak losowanie pivota albo warianty hybrydowe.

To dobry przykład różnicy między średnim a najgorszym przypadkiem. W zadaniu rekrutacyjnym nie wystarczy powiedzieć, że quicksort ma „n log n”. Trzeba doprecyzować, że chodzi najczęściej o średnią złożoność, podczas gdy gwarancja zależy od konkretnej implementacji.

Heap sort i drzewa

Heap sort zapewnia O(n log n) także w najgorszym przypadku i może działać bez dużego bufora pomocniczego. Z kolei operacje na zrównoważonych drzewach wyszukiwania, takich jak dodawanie, usuwanie czy wyszukiwanie, często mają koszt O(log n) dla jednej operacji. Jeśli wykonujemy je dla n elementów, łączny koszt może wynieść właśnie O(n log n).

Trzeba jednak sprawdzić, czy drzewo rzeczywiście pozostaje zrównoważone. Zwykłe drzewo binarne przy pechowej kolejności danych może zamienić się w strukturę przypominającą listę, a wtedy operacje spadają do O(n).

Jak ta klasa wypada na tle innych algorytmów

Sama etykieta złożoności nie mówi, czy program będzie szybki na każdej maszynie. Daje jednak bardzo użyteczne wyobrażenie o tym, jak zachowa się po zwiększeniu danych. Właśnie dlatego porównuję przede wszystkim tempo wzrostu, a dopiero później szczegóły implementacji.

Liczby w tabeli są przybliżeniem liczby operacji, a nie pomiarem czasu w sekundach. Jedna operacja może oznaczać prosty odczyt, ale może też obejmować kosztowne porównanie tekstu. Mimo tego różnica między 20 milionami a bilionem szybko staje się praktycznie odczuwalna.

Dla małych tablic algorytm kwadratowy nie musi być zły. Insertion sort bywa bardzo szybki dla kilkunastu lub kilkudziesięciu prawie uporządkowanych elementów, ponieważ ma małe narzuty i dobrze wykorzystuje lokalność danych. Problem zaczyna się wtedy, gdy ktoś używa go bezrefleksyjnie dla dziesiątek tysięcy rekordów.

Jak rozpoznać tę złożoność w kodzie

Najprościej szukać dwóch elementów. Pierwszy to przejście po wszystkich danych, a drugi to proces, który powtarza się przez około log n poziomów. Taki schemat często pojawia się w rekurencji, sortowaniu przez podział albo przetwarzaniu zrównoważonej struktury.

sortuj(fragment):
    jeśli fragment ma najwyżej jeden element:
        zakończ

    podziel fragment na dwie części
    sortuj lewą część
    sortuj prawą część
    scal obie części

Jedno wywołanie rekurencyjne nie wykonuje tu pracy liniowej, ale cała warstwa scalania przechodzi przez elementy fragmentu. Rekurencja ma około log n poziomów, a praca na poziomach sumuje się do około n, więc otrzymujemy wynik liniowo-logarytmiczny.

Uważaj na pozornie niewinne pętle

Dwie pętle zagnieżdżone zwykle sugerują O(n²), ale nie zawsze. Jeśli wewnętrzna zmienna za każdym razem podwaja albo dzieli swoją wartość, jej liczba obrotów może wynosić O(log n). Na przykład pętla wykonująca operację dla wartości 1, 2, 4, 8 i tak dalej działa logarytmicznie.

i = 1
while i < n:
    wykonaj_operację()
    i = i * 2

Jeśli taki fragment znajduje się wewnątrz pętli przechodzącej po n elementach, wynik może wynieść O(n log n). Nie należy jednak zgadywać na podstawie samego wyglądu kodu. Trzeba sprawdzić, ile razy wykonuje się każda pętla i czy zakres pracy faktycznie zależy od n.

Rekurencja nie zawsze oznacza logarytm

Podział problemu na dwie części może prowadzić do dobrego wyniku, ale tylko wtedy, gdy każda warstwa nie powiela całej pracy w niekontrolowany sposób. Rekurencja T(n) = 2T(n/2) + O(n) prowadzi do O(n log n), natomiast T(n) = 2T(n/2) + O(1) ma koszt O(n).

Najczęstszy błąd początkujących polega na zauważeniu słowa „dzielimy na pół” i automatycznym wpisaniu O(log n). Tymczasem trzeba jeszcze policzyć, ile łącznie pracy wykonują wszystkie gałęzie. Sam podział to za mało, by określić wynik.

Co może zmienić praktyczną wydajność

Złożoność asymptotyczna opisuje zachowanie dla dużych danych i pomija stałe. Dwa algorytmy z tej samej klasy mogą więc działać zauważalnie różnie. Jeden może wykonywać mniej porównań, lepiej wykorzystywać pamięć podręczną procesora albo korzystać z gotowych operacji bibliotecznych.

Znaczenie ma też pamięć. Merge sort często potrzebuje dodatkowego miejsca proporcjonalnego do n, podczas gdy heap sort może pracować niemal w miejscu. W aplikacji webowej wybór może zależeć nie tylko od czasu procesora, lecz także od limitu pamięci, opóźnień serwera i tego, czy dane trzeba sortować jednorazowo, czy wielokrotnie.

Nie zakładałbym również, że ręcznie napisane sortowanie będzie lepsze od funkcji bibliotecznej. Standardowe implementacje są zwykle długo testowane i często używają hybryd, które dla małych fragmentów przełączają się na prostsze algorytmy. Własny kod ma sens wtedy, gdy masz konkretny powód, profil danych i pomiar potwierdzający problem.

Przeczytaj również: System dwójkowy dla programistów - Zrozum bity i bajty!

Kiedy metoda liniowa może wygrać

Granica dla sortowania porównaniowego nie obowiązuje wszystkich możliwych metod. Counting sort, radix sort albo bucket sort mogą osiągać koszt bliski O(n), jeśli dane spełniają określone warunki, na przykład mają ograniczony zakres lub dają się rozłożyć na cyfry.

To nie jest jednak darmowe przyspieszenie. Trzeba zapłacić dodatkowymi założeniami, pamięcią albo bardziej skomplikowaną implementacją. Dla dowolnych obiektów, tekstów i niestandardowych reguł porównywania uniwersalne algorytmy o koszcie liniowo-logarytmicznym zwykle pozostają rozsądnym wyborem.

Jak wykorzystać tę wiedzę podczas nauki programowania

Na początku nie próbowałbym zapamiętywać samych oznaczeń. Lepiej przy każdym algorytmie odpowiedzieć sobie na trzy pytania: ile razy przechodzę przez dane, czy problem maleje przez podział oraz czy liczba gałęzi rekurencji rośnie. Taki sposób myślenia szybciej prowadzi do poprawnej analizy niż nauka tabeli na pamięć.

• Najpierw określ, co oznacza n w danym zadaniu.
• Policz pracę jednej iteracji, jednej warstwy lub jednego wywołania.
• Sprawdź, ile razy powtarza się ten etap.
• Oddziel czas działania od zużycia pamięci.
• Rozważ najlepszy, średni i najgorszy przypadek.
• Jeśli wybierasz między algorytmami, wykonaj prosty benchmark na realistycznych danych.

Najważniejsza lekcja jest prosta. O(n log n) to zazwyczaj bardzo dobry wybór dla ogólnego sortowania i wielu problemów opartych na dzieleniu danych, ale nie jest magiczną obietnicą szybkości. Patrzę na tę klasę jak na bezpieczny punkt wyjścia, a ostateczną decyzję opieram na danych wejściowych, pamięci, gwarancjach najgorszego przypadku i pomiarach.