27
правок
Изменения
Нет описания правки
{{Определение
|definition=
<tex>\mathrm{DTIME}(f(n))</tex> — класс языков <tex>L</tex>, для которых существует детерминированная программа <tex>p : L(p)=L</tex> и для любого <tex>x \in </tex> из <tex>L</tex>, такого что <tex>|x| = n</tex>, выполнено <tex>\mathrm{T}(p,x) = O(f(n))</tex>.
}}
{{Определение
|definition=
<tex>\mathrm{DSPACE}(f(n))</tex> — класс языков <tex>L</tex>, для которых существует детерминированная программа <tex>p : L(p)=L</tex> и для любого <tex>x \in </tex> из <tex>L</tex>, такого что <tex>|x| = n</tex>, выполнено <tex>\mathrm{S}(p,x) = O(f(n))</tex>.
}}
