На нашем дискретном курсе математики в моем университете учитель показывает своим ученикам Ackermann function и назначает ученика для разработки функции на бумаге.Использование функции Аккермана?
Помимо оценки эффективности рекурсии, существует ли функция Ackermann в реальных целях?
Да. Функция (обратная) Аккермана появляется при анализе сложности алгоритмов. Когда это происходит, это означает, что вы можете почти игнорировать этот термин, так как он растет настолько медленно (многое, что лог (log ... log (n) ...)), то есть lg * (n). Например: Minimum Spanning Trees (также here) и Disjoint Set лесное строительство.
также: Davenport-Scinzel sequences
В частности, алгоритм поиска соединения, если вы хотите пример. http://www.yucs.org/~gnivasch/alpha/index.html – Joshua
Но это обратная функция, как насчет реальной функции? –
Я согласен с другим ответом (по Вранг-Вранг) "в теории".
На практике Ackerman не слишком полезен, потому что на практике единственные сложности алгоритма, с которыми вы, как правило, сталкиваетесь, включают в себя 1, N, N^2, N^3 и каждый из них, умноженный на logN. (И так как logN никогда не превышает 64, это в любом случае равно постоянный термин.)
Точка, «на практике», если только ваша сложность алгоритма не «слишком велика», вам не нужна сложность , поскольку доминируют реальные факторы. (Функция, выполняемая в O (обратная-Ackermann), теоретически лучше, чем функция, выполняемая в O (logN) времени, но на практике вы будете измерять две фактические реализации против реальных данных и выбирать, какая из них действительно работает лучше Напротив, теория сложности действительно «имеет значение на практике», например, N против N^2, где эффекты алгоритмической сложности действительно превосходят любые эффекты «реального мира». Я нахожу, что «N» является наименьшей мерой, которая имеет значение на практике .)
Действительно, теоретический анализ дает вам основу для анализа производительности. –
Можете ли вы объяснить, как logN не превышает 64? –
Обычно «журнал» является базой 2. Если log (n) равен 64, значит, у вас есть 2^64 элемента данных. Это гораздо больше, чем на практике; действительно, на 64-битном компьютере у вас есть 64-битные указатели, поэтому вы даже не можете представить более 2^64 байт. – Andrey
Исходным «использованием» функции Аккермана было показать, что существуют функции, которые не являются примитивными рекурсивными, т.е. не могут быть вычислены с использованием только для циклов с заданными верхними пределами.
Функция Ackermann является такой функцией, она слишком быстро растет, чтобы быть примитивной рекурсивной.
Я не думаю, что это действительно практическое применение, оно слишком быстро растет, чтобы быть полезным. Вы даже не можете явно представить числа за пределами (4,3) в разумном пространстве.
https://en.wikipedia.org/wiki/Hyperoperation – starblue