Złożoność obliczeniowa (notacja Big O)

Po co się tego uczymy?

Ten sam problem można rozwiązać na wiele sposobów — jedne będą szybkie dla 10 elementów, ale "położą" program przy 10 milionach elementów, inne będą działać płynnie niezależnie od rozmiaru danych. Złożoność obliczeniowa to sposób opisania, jak czas działania (albo zużycie pamięci) algorytmu rośnie wraz z rozmiarem danych wejściowych. Podstawa programowa wymienia to wprost (INF.04.3.3) i to kluczowa wiedza przy wyborze algorytmu sortowania czy wyszukiwania — tematów z kolejnych dwóch lekcji.

Teoria

Notacja Big O (duże O) opisuje, jak liczba operacji algorytmu rośnie wraz z rozmiarem danych n, w najgorszym możliwym przypadku. Najważniejsze klasy złożoności, od najlepszej do najgorszej:

O(1) — czas stały, niezależny od rozmiaru danych. Np. pobranie elementu tablicy po indeksie: tablica[5] zawsze trwa tyle samo, niezależnie czy tablica ma 10 czy 10 milionów elementów.
O(log n) — czas logarytmiczny. Przy każdym kroku algorytm odrzuca połowę pozostałych danych (tak działa wyszukiwanie binarne z lekcji 27) — podwojenie danych dodaje tylko JEDEN dodatkowy krok.
O(n) — czas liniowy. Jedna pętla przechodząca po wszystkich elementach — podwojenie danych podwaja czas działania.
O(n log n) — typowe dla dobrych algorytmów sortowania (np. sortowanie szybkie w typowym przypadku).
O(n²) — czas kwadratowy. Pętla w pętli, gdzie obie przechodzą po n elementach (np. sortowanie bąbelkowe) — podwojenie danych CZTEROKROTNIE wydłuża czas działania.

Liczy się rząd wielkości, nie dokładna liczba operacji — dlatego stałe współczynniki są pomijane (algorytm wykonujący "2n" operacji i tak jest zapisywany jako O(n)). Ważne jest tempo WZROSTU przy rosnącym n, nie konkretna wartość dla małego n.

W praktyce: dla małych zbiorów danych (kilkanaście, kilkaset elementów) różnica między O(n) a O(n²) często nie jest odczuwalna. Problem pojawia się przy dużych zbiorach — algorytm O(n²) dla miliona elementów wykonuje bilion operacji, co realnie oznacza zawieszenie programu na długie sekundy albo minuty, podczas gdy algorytm O(n log n) poradzi sobie z tym w ułamku sekundy.

Schemat

Jak rośnie liczba operacji wraz z rozmiarem danych (n):

liczba
operacji
   ^
   |                                              O(n^2) - pętla w pętli
   |                                        ,·''
   |                                   ,·''
   |                              ,·''
   |                         ,·''              O(n) - jedna pętla
   |                    ,·''          _,,--''''
   |               ,·''      _,,--''''
   |          ,·''  _,,--''''  O(log n) - np. wyszukiwanie binarne
   |     _,·-''''__,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,, O(1) - stały czas
   |__,,--''''
   +-------------------------------------------------------► rozmiar danych (n)

Im "płaższa" krzywa, tym algorytm lepiej się skaluje dla dużych n.

Przykład z życia

Wyszukiwarka w telefonie, która błyskawicznie znajduje kontakt wśród tysięcy pozycji, korzysta z algorytmów o dobrej złożoności (np. O(log n) dzięki posortowanym danym i wyszukiwaniu binarnemu albo nawet O(1) dzięki tzw. tablicom haszującym). Gdyby przeszukiwała każdy kontakt po kolei (O(n)) na liście milionów rekordów w dużej firmie, różnica w czasie odpowiedzi byłaby wyraźnie odczuwalna dla użytkownika.

Kod (C#)

using System;
using System.Diagnostics;

class Program
{
    // O(1) - czas stały, niezależnie od rozmiaru tablicy
    static int PobierzPierwszy(int[] tablica)
    {
        return tablica[];
    }

    // O(n) - jedna pętla po wszystkich elementach
    static int Suma(int[] tablica)
    {
        int suma = ;
        foreach (int liczba in tablica)
        {
            suma += liczba;
        }
        return suma;
    }

    // O(n^2) - pętla w pętli, obie po n elementach
    static bool MaDuplikaty(int[] tablica)
    {
        for (int i = ; i < tablica.Length; i++)
        {
            for (int j = i + 1; j < tablica.Length; j++)
            {
                if (tablica[i] == tablica[j])
                {
                    return true;
                }
            }
        }
        return false;
    }

    static void Main()
    {
        int[] male = new int[2000];
        Random los = new Random();
        for (int i = ; i < male.Length; i++) male[i] = los.Next(100000);

        var stoper = Stopwatch.StartNew();
        MaDuplikaty(male); // O(n^2) - dla 2000 elementów to już 4 miliony porównań
        stoper.Stop();

        Console.WriteLine($"MaDuplikaty dla {male.Length} elementów: {stoper.ElapsedMilliseconds} ms");
    }
}

Komentarz i wyjaśnienie kodu

PobierzPierwszy zawsze wykonuje jedną operację — to O(1). Suma przechodzi raz przez każdy element — liczba operacji rośnie proporcjonalnie do n, czyli O(n). MaDuplikaty ma pętlę WEWNĄTRZ pętli — dla każdego elementu i sprawdza wszystkie kolejne elementy j, co daje w przybliżeniu n×n operacji, czyli O(n²). Kod mierzy realny czas działania Stopwatch-em — spróbuj zwiększyć rozmiar tablicy z 2000 do 20000 (dziesięciokrotnie) i zobacz, że czas rośnie około 100 razy (bo 10² = 100) — to właśnie znaczy "kwadratowo".

Ćwiczenie samodzielne

Uruchom kod z rozmiarem tablicy 2000, potem 4000, potem 8000 elementów. Zapisz czasy i sprawdź: czy czas rośnie liniowo (2x dane = 2x czas), czy kwadratowo (2x dane = ~4x czas)?

Plac zabaw — wypróbuj online

Poniższy kod wykonuje się od razu w Twojej przeglądarce — nic nie trzeba instalować. Zmień kod i kliknij „Uruchom”.

CSHARP

using System;
using System.Diagnostics;

class Program
{
    // O(1) - czas stały, niezależnie od rozmiaru tablicy
    static int PobierzPierwszy(int[] tablica)
    {
        return tablica[0];
    }

// O(n) - jedna pętla po wszystkich elementach
    static int Suma(int[] tablica)
    {
        int suma = 0;
        foreach (int liczba in tablica)
        {
            suma += liczba;
        }
        return suma;
    }

// O(n^2) - pętla w pętli, obie po n elementach
    static bool MaDuplikaty(int[] tablica)
    {
        for (int i = 0; i < tablica.Length; i++)
        {
            for (int j = i + 1; j < tablica.Length; j++)
            {
                if (tablica[i] == tablica[j])
                {
                    return true;
                }
            }
        }
        return false;
    }

static void Main()
    {
        int[] male = new int[2000];
        Random los = new Random();
        for (int i = 0; i < male.Length; i++) male[i] = los.Next(100000);

var stoper = Stopwatch.StartNew();
        MaDuplikaty(male); // O(n^2) - dla 2000 elementów to już 4 miliony porównań
        stoper.Stop();

Console.WriteLine($"MaDuplikaty dla {male.Length} elementów: {stoper.ElapsedMilliseconds} ms");
    }
}

Zadania do pracy własnej

Określ złożoność (O(1), O(n) czy O(n²)) dla: a) wypisania wszystkich elementów tablicy, b) sprawdzenia czy tablica jest pusta, c) porównania każdego elementu z każdym innym elementem tej samej tablicy.
Napisz dwie wersje funkcji sprawdzającej, czy tablica zawiera duplikaty: jedną O(n²) (jak w przykładzie) i jedną szybszą, wykorzystującą HashSet<int> (powinna wyjść O(n)). Zmierz i porównaj czas obu dla tablicy 20000 elementów.
Znajdź w internecie (albo napisz samodzielnie) implementację wyszukiwania binarnego i zmierz jego czas działania dla posortowanej tablicy 10 milionów elementów, porównując z wyszukiwaniem liniowym (pętla for) tej samej wartości. Skomentuj różnicę, odnosząc się do O(log n) kontra O(n).

Typowe błędy

Ocenianie wydajności "na oko" tylko dla małych danych — algorytm O(n²) może działać błyskawicznie dla 100 elementów i "zawiesić się" na kilka sekund dla 100 000. Zawsze warto pomyśleć, jak duże dane program będzie realnie przetwarzał.

Zagnieżdżanie pętli bez potrzeby — częsty błąd początkujących to pętla w pętli tam, gdzie wystarczyłaby jedna pętla ze słownikiem/zbiorem (Dictionary/HashSet), co zamienia O(n²) na O(n).

Mylenie złożoności czasowej ze złożonością pamięciową — Big O opisuje też, ile DODATKOWEJ PAMIĘCI zużywa algorytm, nie tylko czas. To dwa osobne wymiary — czasem warto poświęcić trochę pamięci (np. na HashSet), żeby zyskać dużo na czasie.

Nawiązanie do egzaminu zawodowego

Złożoność obliczeniowa jest wymieniona wprost w INF.04.3.3 i jest niezbędna do świadomego wyboru algorytmu sortowania i wyszukiwania z INF.04.3.4 — czyli kolejnych dwóch lekcji tego działu.