Использует функцию Аккермана?

Question

На нашем курсе по дискретной математике в моем университете учитель показывает своим ученикам функцию Аккермана и поручает ученику развить эту функцию на бумаге.

Помимо того, что функция Ackermann является эталоном для оптимизации рекурсии, она имеет какое-то реальное применение?

Answer 1

Да. Функция (обратная) Аккермана появляется при анализе сложности алгоритмов. Когда это происходит, это означает, что вы можете почти игнорировать этот термин, так как он растет очень медленно (очень похоже на log (log ... log (n) ...)), т.е. lg * (n). Например: Минимальное остовное дерево (также здесь ) и Разрывный набор лесная конструкция.

Также: Последовательности Давенпорта-Сцинзеля

Answer 2

Первоначальное «использование» функции Аккермана состояло в том, чтобы показать, что существуют функции, которые не являются примитивно-рекурсивными, то есть которые не могут быть вычислены с использованием только циклов for с заранее определенными верхними пределами.

Функция Аккермана - это такая функция, она растет слишком быстро, чтобы быть примитивно-рекурсивной.

Я не думаю, что есть действительно практическое применение, оно растет слишком быстро, чтобы быть полезным. Вы даже не можете явно представить числа за (4,3) в разумном месте.

Answer 3

Я согласен с другим ответом (по wrang-wrang) "в теории".

На практике Аккерман не слишком полезен, потому что на практике единственные сложности алгоритмов, с которыми вы сталкиваетесь, включают 1, N, N ^ 2, N ^ 3, и каждая из них умножается на logN. (И поскольку logN никогда не превышает 64, это, по сути, постоянный термин.)

Дело в том, что «на практике», если сложность вашего алгоритма не будет «в N раз слишком большой», вас не волнует сложность, потому что факторы реального мира будут доминировать. (Функция, которая выполняется в O (inverse-Ackermann), теоретически лучше, чем функция, которая выполняется за O (logN), но на практике вы будете сравнивать две фактические реализации с реальными данными и выбирать, какая из них на самом деле работает лучше). Напротив, теория сложности «имеет значение на практике», например, для N по сравнению с N ^ 2, где эффекты алгоритмической сложности фактически подавляют любые эффекты «реального мира». Я считаю, что «N» является наименьшей мерой, которая имеет значение на практике. .)