#separator:tab
#html:false
#deck:Złożoność obliczeniowa — notacja O
#columns:Front Back
Definicja notacji O Szacuje górną granicę czasu działania algorytmu
O(1) Stała złożoność, np. dostęp do elementu tablicy
O(log n) Logarytmiczna, np. wyszukiwanie binarne
O(n) Liniowa, np. przejście przez listę
O(n log n) Liniowo-logarytmiczna, np. sortowanie przez scalanie
O(n²) Kwadratowa, np. sortowanie bąbelkowe
Złożoność sortowania szybkiego Sortowanie przez porównania: średnio O(n log n)
Złożoność sortowania bąbelkowego O(n²) dla każdego przypadku
Złożoność sortowania przez scalanie Zawsze O(n log n)
Złożoność sortowania stogowego Zawsze O(n log n)
Złożoność sortowania przez wstawianie O(n) w najlepszym, O(n²) w średnim
Złożoność sortowania szybkiego (quicksort) Średnio O(n log n), pesymistycznie O(n²)
Złożoność sortowania przez zliczanie O(n + k) dla danych o małym zakresie
Złożoność wyszukiwania binarnego O(log n) w posortowanej tablicy
Złożoność wyszukiwania liniowego O(n) w przypadku pesymistycznym
Złożoność wyszukiwania w tablicy haszującej O(1) dla pojedynczego klucza
Cechy notacji O Ignoruje stałe, skupia się na trendzie wzrostu
Przykład algorytmu o złożoności stałej O(1) – stały czas