Złożoność obliczeniowa
Słownik kwalifikacji INF.03 - Tworzenie i administrowanie stronami i aplikacjami internetowymi oraz bazami danych
Co to jest złożoność obliczeniowa?
Złożoność obliczeniowa określa, jak rośnie liczba operacji wykonywanych przez algorytm wraz ze wzrostem rozmiaru danych wejściowych. Najczęściej zapisuje się ją za pomocą notacji O, np. O(n), O(n²), O(log n).
W egzaminach zawodowych zwykle chodzi o oszacowanie, ile razy algorytm musi wykonać podstawową operację, np. porównanie, przypisanie lub przejście pętli.
Przykład: O(n)
Jeżeli algorytm sprawdza każdy element tablicy dokładnie raz, jego złożoność jest liniowa:
Dla 10 liczb wykonuje około 10 kroków.
Dla 100 liczb wykonuje około 100 kroków.
Dla n liczb wykonuje około n kroków.
Taki algorytm ma złożoność O(n).
Najczęstsze klasy złożoności
O(1)- czas stały, niezależny od liczby danych,O(log n)- czas logarytmiczny, np. wyszukiwanie binarne,O(n)- czas liniowy, np. przeglądanie całej tablicy,O(n²)- czas kwadratowy, np. dwie zagnieżdżone pętle po n elementów,O(n!)- czas silniowy, bardzo wolny dla dużych danych.
Ważne na egzaminie
Przy wyszukiwaniu najmniejszej lub największej wartości w nieposortowanym zbiorze trzeba obejrzeć wszystkie elementy. Dlatego standardowy algorytm ma złożoność O(n), a nie O(n²).