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

Question

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

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

Answer 1

ДА.(Обратная) Функция Аккермана появляется при анализе сложности алгоритмов.Когда это происходит, это означает, что вы можете почти игнорировать этот термин, поскольку он растет очень медленно (очень похоже на 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" является наименьшей мерой, которая имеет значение на практике.)