Big-O opisuje, jak czas wykonania lub pamięć algorytmu rosną wraz z rozmiarem wejścia n. Oddaje worst-case zachowanie asymptotyczne, ignorując stałe i wyrazy niższego rzędu.
Zależy nam na tempie wzrostu, a nie na dokładnej liczbie kroków. O(2n + 5) to po prostu O(n), ponieważ wraz ze wzrostem n, stałe i mniejsze wyrazy przestają mieć znaczenie.
| Big-O | Nazwa | Przykład |
|---|
| O(1) | stała | array index lookup |
| O(log n) | logarytmiczna | binary search |
| O(n) | liniowa | skanowanie listy |
| O(n log n) | linearytmiczna | merge sort |
| O(n²) | kwadratowa | zagnieżdżone pętle |
| O(2ⁿ) | wykładnicza | naive subsets |
def has_duplicate(nums):
for i in range(len(nums)): # outer loop: n
for j in range(i + 1, len(nums)): # inner loop: n
if nums[i] == nums[j]:
return True
return False
# nested loops -> O(n^2) time, O(1) space
Big-O ukrywa stałe: algorytm O(n) z dużą stałą może przegrać z O(n log n) na małych wejściach. Śledź również złożoność space, a nie tylko time.
Big-O pozwala porównywać algorytmy bez uruchamiania ich ani martwienia się o sprzęt.
Przewiduje, które rozwiązania przetrwają, gdy wejścia rosną z setek do milionów — różnica między funkcją, która się skaluje, a tą, która się timeout'uje.
To jest słownictwo, którego każdy inżynier używa, aby rozumować o wydajności.