klasy złożoności

[pojęcie] Zbiory problemów obliczeniowych o podobnych złożonościach obliczeniowych.

Klasy złożoności czasowej

Klasa złożoności	Model obliczeń	Złożoność czasowa
P	Deterministyczna maszyna Turinga	O(n^X) – złożoność wielomianowa
NP	Niedeterministyczna maszyna Turinga	O(n^X) – złożoność wielomianowa
EXPTIME	Deterministyczna maszyna Turinga	O(Xⁿ) – złożoność wykładnicza
NEXPTIME	Niedeterministyczna maszyna Turinga	O(Xⁿ) – złożoność wykładnicza

W powyższych wzorach 'n' określa liczbę danych wejściowych, natomiast 'X' jest stałą.

DTIME	Złożoność czasowa algorytmu, rozpatrywana na deterministycznej maszynie Turinga. (pojęcie)
NTIME	Złożoność czasowa algorytmu, rozpatrywana na niedeterministycznej maszynie Turinga. (pojęcie)

Wszystkie teksty są chronione prawami autorskimi. Kopiowanie lub rozpowszechnianie treści poza niniejszym serwisem jest zabronione.

Powyższe ograniczenie nie dotyczy autora opracowania, któremu przysługuje prawo do rozpowszechniania własnego tekstu wedle własnego uznania.