Panel użytkownika
Nazwa użytkownika:
Hasło:
Nie masz jeszcze konta?
Opracował: Piotr DejaVu Szawdyński
Pojęcia

DTIME

[pojęcie] Złożoność czasowa algorytmu, rozpatrywana na deterministycznej maszynie Turinga.

Opis szczegółowy

DTIME określa złożoność czasową algorytmu, rozpatrywanego na deterministycznej maszynie Turinga. Zapis ten wykorzystuje się głównie do opisywania klas złożoności.

Zapis DTIME(f(n)) oznacza, że rozpatrywanym modelem obliczeń jest deterministyczna maszyna Turinga, której złożoność czasowa algorytmu wynosi f(n), gdzie 'n' określa liczbę danych wejściowych. Determinizm w maszynie Turinga oznacza, że w wyniku działania algorytmu uzyskujemy zawsze wartość logiczną prawda lub fałsz.

Dodatkowe informacje

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

Zagadnienia powiązane

NTIMEZłożoność czasowa algorytmu, rozpatrywana na niedeterministycznej maszynie Turinga. (pojęcie)
klasy złożonościZbiory problemów obliczeniowych o podobnych złożonościach obliczeniowych. (pojęcie)
problem PZnalezienie rozwiązania wymaga złożoności obliczeniowej wielomianowej. (pojęcie)

Linki zewnętrzne