Lekcja: "Algorytmy sortujące - sortowanie przez wstawianie, sortowanie przez wybór"
Czasowa złożoność obliczeniowa
Czasowa złożoność obliczeniowa (ang. computational complexity) algorytmu sortującego (istnieje również złożoność pamięciowa) – określa statystycznie czas wykonywania algorytmu w zależności od liczby danych wejściowych.
Czasowa złożoność obliczeniowa wyrażana jest liczbą tzw. operacji dominujących, czyli takich, które mają bezpośredni wpływ na czas wykonywania algorytmu. Dzięki takiemu podejściu uniezależnia się czasową złożoność obliczeniową od szybkości komputera, na którym dany algorytm jest realizowany.
Złożoność obliczeniową charakteryzowana jest przy pomocy tzw. notacji O (omikron). Zapis O( ) określamy mianem klasy złożoności obliczeniowej algorytmu.
Klasa czasowej złożoności obliczeniowej umożliwia porównywanie wydajności różnych algorytmów sortujących. Z reguły proste algorytmy posiadają wysoką złożoność obliczeniową - długo dochodzą do wyniku końcowego.
Algorytmy bardziej skomplikowane posiadają mniejszą złożoność obliczeniową - szybko dochodzą do rozwiązania.
