Теорема об ускорении
 |
В теории сложности вычислений теорема об ускорении — это теорема , которая для любого алгоритма (определённого класса) демонстрирует существование более эффективного алгоритма, решающего ту же задачу.
Примеры:
- Теорема линейного ускорения , согласно которой требования к пространству и времени машины Тьюринга, решающей проблему решения, могут быть уменьшены с помощью мультипликативного постоянного коэффициента.
- Теорема Блюма об ускорении , обеспечивающая ускорение по любой вычислимой функции (а не только линейной, как в предыдущей теореме).
См. также
[ редактировать ]- Закон Амдала — теоретическое ускорение задержки выполнения задачи при фиксированной рабочей нагрузке, которого можно ожидать от системы, ресурсы которой улучшены.
Ссылки
[ редактировать ] | Эта по информатике статья незавершена . Вы можете помочь Википедии, расширив ее . |