Złożoność czasowa
W algorytmiki , czas złożoność jest miarą czasu wykorzystane przez algorytm , wyrażone w funkcji wielkości wejściowych. Czas liczy liczbę kroków obliczeniowych przed uzyskaniem wyniku.
Zwykle czas odpowiadający wejściom o rozmiarze n jest najdłuższym czasem spośród czasów wykonania danych wejściowych o tej wielkości; w najgorszym przypadku mówimy o złożoności. Badania złożoności dotyczą w większości przypadków zachowania asymptotycznego , gdy wielkość wpisów dąży do nieskończoności, a obecnie używa się notacji duże O Landaua .
Ponieważ złożoność czasowa jest najpowszechniejszą miarą algorytmów, czasami po prostu mówimy o złożoności algorytmu, ale są też inne miary, takie jak złożoność przestrzeni .
Obliczanie złożoności algorytmu, a zwłaszcza złożoności czasowej, bywa niekiedy złożone, a badanie samo w sobie stanowi dyscyplinę: analizę złożoności algorytmów .
Definicje
Złożoność czasowa liczy liczbę kroków obliczeniowych. Istnieje kilka sposobów definiowania tych kroków, na przykład liczba operacji w maszynie RAM lub bardziej teoretyczne pomiary, takie jak liczba porównań w przypadku algorytmu sortowania lub liczba kroków maszyny Turinga .
Badanie czasu obliczeń często polega na określeniu górnej granicy liczby kroków, wyrażonej przez rząd wielkości. Na przykład w przypadku algorytmu sortowania scalającego mówimy o złożoności w , co oznacza, że istnieje taka stała , że dla dowolnego wejścia o rozmiarze liczba kroków będzie mniejsza niż .
Czas, jak zdefiniowano powyżej, jest powiązany z rzeczywistym czasem obliczeniowym, ale jest bardziej abstrakcyjnym pomiarem, który zależy od algorytmu i danych wejściowych, ale jest niezależny np. Od mocy komputera (liczymy kroki obliczeniowe, a nie sekundy ) .
Lista zawiłości w czasach klasycznych
| Nazwisko | Czas obliczeń ( T ( n )) | Przykład czasu obliczeń | Przykładowe algorytmy |
|---|---|---|---|
| Stały | O (1) | 10 | Zmniejszenie klucza w stercie Fibonacciego |
| Logarytmiczna | O (log n ) | log n , log ( n 2 ) | Wyszukiwanie dychotomiczne |
| Liniowy | O ( n ) | nie | Wyszukiwanie sekwencyjne , prosty algorytm znajdowania najmniejszego elementu tablicy |
| Linearithmic | O ( n log n ) | n log n , log n ! | Sortuj przez scalanie |
| Kwadratowy | O ( nr 2 ) | n 2 | Sortuj według wstawienia |
| Sześcienny | O ( nr 3 ) | nr 3 | Naiwny algorytm mnożenia macierzy . |
| Wielomian | 2 O (log n ) = poli ( n ) | n , n log n , n 10 | Algorytm Karmarkara , test pierwszości AKS |
| Wykładniczy | 2 o ( n ) | 2 n 1/3 | Najlepsze algorytmy do faktorowania liczb całkowitych |
| Wykładniczy | 2 O ( n ) | 1,1 n , 10 n | Algorytm brutalnej siły , na przykład dla problemu komiwojażera |
Związek z teorią złożoności problemów
Teoria złożoności problemów, często nazywana teorią złożoności , jest dyscypliną polegającą na klasyfikowaniu problemów algorytmicznych według trudności według różnych miar. Pewne klasy złożoności są definiowane przez czas obliczeniowy, na przykład problemy klasy P to te, dla których istnieje algorytm, którego złożoność w czasie jest ograniczona wielomianem.
Wśród klas problemów definiowanych przez czas liczy się zwłaszcza P , NP i EXPTIME . Koncentrując się na algorytmach probabilistycznych , otrzymujemy klasy takie jak BPP .
Alternatywne miary złożoności
Alternatywą dla złożoności w najgorszym przypadku jest obliczenie średniej złożoności algorytmu, czyli czasu, jaki algorytm zajmie średnio na losowo wylosowanym wpisie, na przykład według rozkładu rozkładu. Możemy również przytoczyć płynną analizę algorytmów i ogólną złożoność .
Pewne miary złożoności nie są bezpośrednio związane z czasem obliczeń, na przykład w przypadku złożoności w przestrzeni, to znaczy miary pamięci potrzebnej do wykonania obliczenia.
Uwagi i odniesienia
- Widok (w) Thomas H. Cormen , Charles E. Leiserson , Ronald L. Rivest i Clifford Stein , Introduction to Algorithms , MIT Press ,2009, 3 e ed. [ szczegóły wydania ], rozdz. 2.2, s. 23.
- Sylvain Perifel , Złożoność algorytmiczna , Elipsy ,2014, 432 s. ( ISBN 9782729886929 , czytaj online ) , rozdz. 2.1 („Deterministyczny czas”).
- (w) Thomas H. Cormen , Charles E. Leiserson , Ronald L. Rivest i Clifford Stein , Wprowadzenie do algorytmów , MIT Press ,2009, 3 e ed. [ szczegóły wydania ], rozdz. 34, „ Kompletność NP ”.