#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