Czym jest notacja Big O?
Notacja Big O opisuje, jak rośnie liczba operacji wykonywanych przez algorytm wraz ze wzrostem rozmiaru danych wejściowych n. Nie mierzy dokładnego czasu w sekundach, lecz tempo wzrostu kosztu algorytmu.
W egzaminach najczęściej dotyczy złożoności czasowej, czyli tego, ile operacji wykonuje program dla coraz większych danych.
Najczęstsze oznaczenia
- O(1) - złożoność stała; liczba operacji nie zależy od
n. - O(log n) - złożoność logarytmiczna; np. wyszukiwanie binarne.
- O(n) - złożoność liniowa; liczba operacji rośnie proporcjonalnie do liczby danych.
- O(n²) - złożoność kwadratowa; często przy dwóch zagnieżdżonych pętlach.
Złożoność liniowa O(n)
Algorytm ma złożoność O(n), gdy dla n elementów wykonuje liczbę operacji proporcjonalną do n. Jeśli danych jest dwa razy więcej, zwykle pracy też jest około dwa razy więcej.
Przykład:
for element in lista:
print(element)
Pętla przechodzi przez każdy element listy dokładnie raz, więc jej złożoność to O(n).
Jak rozpoznawać na egzaminie?
Jeżeli pytanie brzmi o liniową złożoność algorytmu, poprawnym oznaczeniem jest:
O(n)
Warto zapamiętać: słowo liniowa oznacza zależność wprost proporcjonalną do liczby danych wejściowych.