C# / .NET Kompendium PLEN
.NET / C# / Algorytmy, struktury danych

Big-O i podstawowe struktury danych

Co to jest notacja Big-O

Big-O opisuje, jak czas wykonania (albo zużycie pamięci) algorytmu rośnie względem rozmiaru danych wejściowych (n), w najgorszym przypadku, ignorując stałe czynniki i mniej znaczące składniki.

// O(1) - stały czas, niezależnie od rozmiaru kolekcji
int first = list[0];

// O(n) - czas rośnie LINIOWO z rozmiarem
foreach (var item in list) { Console.WriteLine(item); }

// O(n²) - czas rośnie KWADRATOWO (pętla w pętli)
foreach (var a in list)
    foreach (var b in list)
        Compare(a, b);

// O(log n) - czas rośnie logarytmicznie (np. wyszukiwanie binarne)
int index = Array.BinarySearch(sortedArray, target);

Złożoności podstawowych operacji na kolekcjach .NET

Operacja List<T> Dictionary<K,V> HashSet<T> LinkedList<T>
Dostęp po indeksie O(1) - - O(n)
Wyszukiwanie po wartości O(n) O(1)* O(1)* O(n)
Dodanie na koniec O(1)** O(1)* O(1)* O(1)
Dodanie na początek/w środku O(n) - - O(1)
Usunięcie O(n) O(1)* O(1)* O(1)

Amortyzowane O(1) dla struktur haszowanych - w praktyce prawie zawsze stały czas, ale w rzadkich przypadkach kolizji może być gorzej. *List<T>.Add() jest O(1) amortyzowane - czasem trzeba powiększyć wewnętrzną tablicę, co jest O(n), ale zdarza się rzadko.

Co właściwie znaczy zapis O(...)

"O" pochodzi od "Order of" (rząd wielkości) - matematyczna notacja opisująca, jak szybko rośnie czas wykonania (albo pamięć) algorytmu, gdy rozmiar danych wejściowych rośnie. Nie mówi, ile to jest konkretnie milisekund - mówi o tempie wzrostu względem n.

n to zawsze rozmiar danych wejściowych - liczba elementów w tablicy, liczba wierszy w bazie, długość stringa - cokolwiek, co "skaluje się" w Twoim problemie.

Kluczowa intuicja: Big-O odpowiada na pytanie "co się stanie, jeśli podwoję dane wejściowe?" - nie "jak szybko działa dla 10 elementów", ale "jak zachowanie zmienia się, gdy n rośnie do nieskończoności".

O(1) - czas stały

Czas wykonania nie zależy od n - niezależnie czy masz 10 elementów czy 10 milionów, operacja trwa tyle samo.

int[] numbers = new int[1_000_000];

int first = numbers[0];             // O(1) - dostęp po indeksie, ZAWSZE jeden krok
int last = numbers[^1];             // O(1) - to samo, niezależnie od rozmiaru tablicy
bool isEmpty = numbers.Length == 0; // O(1) - Length jest już zapisane, nie liczone na nowo

Ważna pułapka pojęciowa: O(1) nie znaczy "szybkie" w sensie absolutnym - znaczy tylko "stała liczba kroków". Coś, co robi 1000 operacji, ale zawsze 1000, niezależnie od n, to wciąż O(1):

// To JEST O(1), mimo że robi 1000 iteracji - liczba iteracji jest STAŁA, nie zależy od n
int Sum1000FixedNumbers()
{
    int sum = 0;
    for (int i = 0; i < 1000; i++) sum += i; // ZAWSZE 1000, obojętnie jakie dane wejściowe
    return sum;
}

O(n) - czas liniowy

Czas wykonania rośnie proporcjonalnie do n - jeśli podwoisz dane wejściowe, operacja zajmie (z grubsza) dwa razy dłużej.

int Sum(int[] array) // O(n)
{
    int sum = 0;
    foreach (var n in array) // MUSI odwiedzić KAŻDY element - jeden raz
        sum += n;
    return sum;
}

Dla tablicy o 10 elementach - 10 kroków. Dla 1000 elementów - 1000 kroków. Dla miliona - milion kroków. Liczba operacji skaluje się razem z n, w stosunku 1:1 (stąd "liniowy" - jak linia na wykresie).

bool Contains(int[] array, int target) // O(n) - w NAJGORSZYM przypadku
{
    foreach (var n in array)
        if (n == target) return true; // może znaleźć od razu (best case), albo dopiero na końcu (worst case)
    return false;
}

Ważne: Big-O zwykle opisuje najgorszy przypadek (worst case) - Contains może teoretycznie znaleźć element na pierwszej pozycji (1 krok), ale Big-O mówi o granicy górnej, czyli sytuacji, gdy trzeba przejrzeć wszystko (element na końcu albo go nie ma).

Wizualne porównanie - jak rosną razem z n

n (rozmiar danych) O(1) - liczba kroków O(n) - liczba kroków
10 1 10
100 1 100
10 000 1 10 000
1 000 000 1 1 000 000

O(1) to płaska linia na wykresie - zawsze ta sama wysokość. O(n) to linia ukośna - rośnie równo z n.

Częsty błąd - "jedna pętla = automatycznie O(n)"

To jest uproszczenie, które czasem jest prawdą, ale nie zawsze - liczy się, ile razy odwiedzasz n elementów, nie liczba pętli w kodzie:

// JEDNA pętla, ale O(n) - odwiedza każdy element RAZ
foreach (var x in array) { Console.WriteLine(x); }

// DWIE pętle, ale WCIĄŻ O(n) - każda pętla osobno przechodzi przez n, więc n + n = 2n,
// a stałe czynniki (2) IGNORUJEMY w Big-O
foreach (var x in array) { /* ... */ }
foreach (var x in array) { /* ... */ }

// JEDNA pętla, ale O(1) - liczba iteracji ma STAŁY GÓRNY LIMIT, niezależny od "n"
int[] fixedFive = { 1, 2, 3, 4, 5 };
for (int i = 0; i < fixedFive.Length; i++)
{
    Console.WriteLine(fixedFive[i]); // fixedFive.Length jest ZAWSZE 5, nie zmienna "n"
}

Ostatni przykład to zresztą częste pytanie-pułapka: "Czy pętla for jest zawsze O(n)?" - odpowiedź: nie, liczy się, czy górna granica pętli zależy od rozmiaru danych wejściowych, czy jest stałą. Pętla po tablicy o zawsze-znanym, sztywnym rozmiarze (tu: 5) to O(1), niezależnie od tego, że technicznie jest to "pętla po tablicy".

Subtelniejszy przypadek - pętla ograniczona Math.Min():

// Nadal O(1) - liczba iteracji jest OGRANICZONA Z GÓRY przez stałą (5),
// mimo że wyrażenie odwołuje się do array.Length
int limit = Math.Min(5, array.Length);
for (int i = 0; i < limit; i++)
{
    Console.WriteLine(array[i]);
}
Jeśli array.Length = 3      → limit = 3   → 3 kroki
Jeśli array.Length = 1000   → limit = 5   → 5 kroków (ograniczone przez stałą!)
Jeśli array.Length = 10 000 → limit = 5   → 5 kroków (ograniczone przez stałą!)

To jest dokładnie ten sam mechanizm, na którym oparte jest np. Take(5) w LINQ - bierze maksymalnie 5 elementów, bez względu na to, czy kolekcja ma 5 czy 5 milionów.

Dlaczego ignorujemy stałe czynniki

2n i n to wciąż to samo O(n) - Big-O interesuje tempo wzrostu, nie precyzyjną liczbę operacji. Dla dużych n, różnica między n a 2n (dwukrotność) jest nieistotna w porównaniu do różnicy między n a n² (kwadrat) - to drugie rośnie znacznie szybciej i to jest sedno, o czym Big-O informuje.

n = 1000:
2n    = 2 000
n     = 1 000
n²    = 1 000 000   ← O(n²) jest dramatycznie gorsze, niezależnie od stałych czynników

Praktyczny przykład - dlaczego to ma znaczenie

// ❌ O(n²) - dla każdego zamówienia, PRZESZUKUJE całą listę klientów
public List<OrderWithCustomer> Combine(List<Order> orders, List<Customer> customers)
{
    var result = new List<OrderWithCustomer>();
    foreach (var order in orders) // n razy
    {
        var customer = customers.FirstOrDefault(c => c.Id == order.CustomerId); // m operacji - LINIOWE przeszukanie!
        result.Add(new OrderWithCustomer(order, customer));
    }
    return result;
} // Całość: O(n * m)

// ✅ O(n) - jednorazowe zbudowanie słownika, potem O(1) dostęp
public List<OrderWithCustomer> Combine(List<Order> orders, List<Customer> customers)
{
    var customerById = customers.ToDictionary(c => c.Id); // O(m) - JEDEN raz

    var result = new List<OrderWithCustomer>();
    foreach (var order in orders) // n razy
    {
        customerById.TryGetValue(order.CustomerId, out var customer); // O(1) każde wyszukanie!
        result.Add(new OrderWithCustomer(order, customer));
    }
    return result;
} // Całość: O(n + m)

Dla 10 000 zamówień i 1000 klientów: pierwsza wersja to 10 milionów operacji porównania, druga to 11 000. To jest różnica, która na produkcji przechodzi z "działa błyskawicznie" do "timeout po 30 sekundach".

Złożoność pamięciowa (Space Complexity)

Big-O opisuje też zużycie pamięci, nie tylko czas:

// O(1) pamięci dodatkowej - modyfikuje w miejscu
void ReverseInPlace(int[] array)
{
    Array.Reverse(array);
}

// O(n) pamięci dodatkowej - tworzy NOWĄ tablicę
int[] ReverseCopy(int[] array)
{
    return array.Reverse().ToArray();
}

Typowe klasy złożoności - od najlepszej do najgorszej

O(1)      < O(log n) < O(n) < O(n log n) < O(n²) < O(2ⁿ) < O(n!)
konstant.   logarytm.  linio.  liniowo-log.  kwadr.  wykładn.  faktorialna

Praktyczne przykłady algorytmów: - O(log n) - wyszukiwanie binarne w sortowanej tablicy - O(n log n) - efektywne algorytmy sortowania (Array.Sort, quicksort, mergesort) - O(n²) - naiwne sortowanie bąbelkowe, zagnieżdżone pętle po tej samej kolekcji

Dlaczego to jest istotne na rozmowach SE III

To nie jest pytanie o "znajomość teorii dla teorii" - w praktyce chodzi o rozpoznanie konkretnych antywzorców w kodzie, jak przykład z FirstOrDefault w pętli wyżej. Najczęstsze pytanie-pułapka: "Co jest nie tak z tym kodem?" z fragmentem zawierającym zagnieżdżone Where/FirstOrDefault po niezindeksowanej kolekcji - dobra odpowiedź rozpoznaje złożoność kwadratową i proponuje Dictionary/HashSet jako rozwiązanie.

Postaw mi kawę