Макеты страниц
Распознанный текст, спецсимволы и формулы могут содержать ошибки, поэтому с корректным вариантом рекомендуем ознакомиться на отсканированных изображениях учебника выше
Также, советуем воспользоваться поиском по сайту, мы уверены, что вы сможете найти больше информации по нужной Вам тематике
Рассмотрим общие функции $f: \mathbf{N} \rightarrow \mathbf{N}$. Теория вычислимости использует несколько шкал роста для таких функций, из которых наиболее полезны две: $f$ может быть ограничена сверху некоторой рекурсивной функцией (например, когда она сама рекурсивна) или полиномом (например, когда она вычислима за полиномиальное время). Кажется, что линейный рост сложности не совсем соответствует настоящему контексту. Однако это впечатление обманчиво, по крайней мере, если разрешено переупорядочение $\mathbf{N}$. В действительности мы имеем
