Złożoność obliczeniowa — notacja O

18 fiszek

🎓 Ucz się 🧩 Dopasuj pary
📥 CSV 📄 TXT
1
Definicja notacji O
Szacuje górną granicę czasu działania algorytmu
2
O(1)
Stała złożoność, np. dostęp do elementu tablicy
3
O(log n)
Logarytmiczna, np. wyszukiwanie binarne
4
O(n)
Liniowa, np. przejście przez listę
5
O(n log n)
Liniowo-logarytmiczna, np. sortowanie przez scalanie
6
O(n²)
Kwadratowa, np. sortowanie bąbelkowe
7
Złożoność sortowania szybkiego
Sortowanie przez porównania: średnio O(n log n)
8
Złożoność sortowania bąbelkowego
O(n²) dla każdego przypadku
9
Złożoność sortowania przez scalanie
Zawsze O(n log n)
10
Złożoność sortowania stogowego
Zawsze O(n log n)
11
Złożoność sortowania przez wstawianie
O(n) w najlepszym, O(n²) w średnim
12
Złożoność sortowania szybkiego (quicksort)
Średnio O(n log n), pesymistycznie O(n²)
13
Złożoność sortowania przez zliczanie
O(n + k) dla danych o małym zakresie
14
Złożoność wyszukiwania binarnego
O(log n) w posortowanej tablicy
15
Złożoność wyszukiwania liniowego
O(n) w przypadku pesymistycznym
16
Złożoność wyszukiwania w tablicy haszującej
O(1) dla pojedynczego klucza
17
Cechy notacji O
Ignoruje stałe, skupia się na trendzie wzrostu
18
Przykład algorytmu o złożoności stałej
O(1) – stały czas