« klasy złożoności, pojęcie, C++ »
klasy złożoności - Zbiory problemów obliczeniowych o podobnych złożonościach obliczeniowych. (pojęcie)
Panel użytkownika
Nazwa użytkownika:
Hasło:
Nie masz jeszcze konta?
Zarejestruj się!
Opracował: Piotr DejaVu Szawdyński

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ściModel obliczeńZłożoność czasowa
PDeterministyczna maszyna TuringaO(nX) – złożoność wielomianowa
NPNiedeterministyczna maszyna TuringaO(nX) – złożoność wielomianowa
EXPTIMEDeterministyczna maszyna TuringaO(Xn) – złożoność wykładnicza
NEXPTIMENiedeterministyczna maszyna TuringaO(Xn) – złożoność wykładnicza

Dodatkowe informacje

  • P = DTIME(nX)
  • NP = NTIME(nX)
  • EXPTIME = DTIME(Xn)
  • NEXPTIM = NTIME(Xn)
W powyższych wzorach 'n' określa liczbę danych wejściowych, natomiast 'X' jest stałą.

Zagadnienia powiązane

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

Linki zewnętrzne