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(n^X) = P
DTIME(Xⁿ) = EXPTIME

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

Zagadnienia powiązane

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

Linki zewnętrzne

http://en.wikipedia.org/wiki/DTIME

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.