INF.04 · C# · lekcja 24

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

Policz operacje zamiast zgadywać czas

  • Zrozum
  • Sprawdź
  • Napisz sam

Po tej lekcji: policz operacje zamiast zgadywać czas

Dzisiaj zrobisz konkretną rzecz

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.

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.

Sprawdź w działaniu

Policz operacje zamiast zgadywać czas

Najpierw przewidź wynik. Zmień dane w modelu i porównaj efekt. Spróbuj także przypadku granicznego, a nie tylko pierwszego poprawnego przykładu.

Ta interakcja wymaga włączonego JavaScriptu.

Model pokazuje wybraną zasadę. Nie uruchamia ani nie ocenia wklejonego kodu C#.

1. Przygotuj i uruchom własny projekt

2. Najpierw mały przykład

Wykonaj tę próbę przed dłuższym rozwiązaniem. Dwie pełne pętle dają n*n iteracji. Big O to asymptotyczne ograniczenie wzrostu, nie liczba milisekund; trzeba wskazać analizowany przypadek. Nie każda pętla zagnieżdżona oznacza n².

Program.cscsharp
foreach (int n in new[] { 10, 20, 40 })
{
    long licznik = 0;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++) licznik++;
    Console.WriteLine($"{n}: {licznik}");
}
Wynik
10:100
20:400
40:1600
  1. Co sprawdzić? Zmień jedną wartość i przed uruchomieniem zapisz przewidywany rezultat. Porównaj go z opisem wyniku; przy błędzie wróć do konkretnej instrukcji.

Jak to działa — 1

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.

Jak to działa — 2

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 danych narzut programu może przysłonić różnicę złożoności. Dla n=1 000 000 samo n² wynosi10¹². Nie przeliczamy tego automatycznie na sekundy: rzeczywisty czas zależy od operacji, sprzętu i implementacji. Porównuj wzrost liczby operacji i osobno wykonuj pomiary.

3. Pełny przykład — czytaj od Main

Teraz zastąp Program.cs tym programem. Zanim uruchomisz, znajdź dane wejściowe, operację i miejsce prezentacji wyniku. W tym wariancie zachowujemy jawny Main. Nie wklejaj kilku pełnych programów do jednego pliku.

Program.cs — osobne uruchomieniecsharp
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");
    }
}
  1. Prześledź kod 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".

Sprawdź, zanim przepiszesz cały program

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.

Ćwiczenie z pomocą · samodzielna praca

4. Teraz Twoja zmiana

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)?

Oczekiwany rezultat
Spełnij warunki polecenia. Zapisz wejście, otrzymany wynik i wyjaśnij, która część kodu za niego odpowiada.
Potrzebujesz pomocy? Rozwiązuj krok po kroku.
Krok 1 — pokaż podpowiedź

Wróć do podstawowej formy oraz objaśnienia: Dwie pełne pętle dają n*n iteracji. Big O to asymptotyczne ograniczenie wzrostu, nie liczba milisekund; trzeba wskazać analizowany przypadek. Nie każda pętla zagnieżdżona oznacza n².

Krok 2 — pokaż podpowiedź

Zmień tylko część potrzebną do polecenia. Zachowaj działającą wersję przed zmianą i uruchamiaj po każdym małym etapie.

Krok 3 — pokaż podpowiedź

Sprawdź przypadek zwykły i graniczny; porównaj z regułą: 10:100 20:400 40:1600

Otwórz tylko tyle podpowiedzi, ile potrzebujesz. Po każdym kroku wróć do zadania i sprawdź wynik.

5. Sprawdź rozumienie, nie tylko uruchomienie

Dalej na swoim koncie

Rozgrzewki, quiz i zadania są w biurku ucznia.

Teoria jest otwarta dla wszystkich. Żeby rozwiązywać zadania, zapisywać szkice i widzieć swój postęp, zaloguj się.

Zaloguj się →
Źródła i dalsza nauka