Изменения

Перейти к: навигация, поиск

Сложностные классы. Вычисления с оракулом

9 байт убрано, 19:10, 4 сентября 2022
м
rollbackEdits.php mass rollback
Слож­ность ал­го­рит­ма - ве­ли­чи­на, ха­ра­к­те­ри­зу­ющая дли­ну опи­са­ния ал­го­рит­ма или гро­мо­зд­кость про­цес­сов его при­ме­не­ния к ис­хо­дным дан­ным.
В основных понятиях теории сложности используются такие параметры величины как время работы и объем затрачиваемой памяти. 
{{Определение
|definition=
{{Определение
|definition=
<tex>\mathrm{TS}(f,g)</tex> — класс языков <tex>L</tex>, для которых существует детерминированная программа <tex>p</tex> такая, что <tex>L(p)=L</tex> и для любого <tex>x</tex> из <tex>L</tex> выполнено <tex>\mathrm{T}(p,x) = O(f(n))</tex> и <tex>\mathrm{S}(p,x) = O(g(n))</tex>, где <tex>x</tex> — длина входа.</tex>
}}
1632
правки

Навигация