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.