アッカーマン関数の使用？

Question

私の大学の個別の数学コースでは、教師は生徒にアッカーマン関数を示します生徒に紙の上の機能を開発するよう割り当てます。

再帰最適化のベンチマークであることに加えて、アッカーマン関数には実際の用途がありますか？

Answer 1

はい。 （逆）アッカーマン関数は、アルゴリズムの複雑度分析に現れます。その場合、その用語は非常にゆっくりと成長するため、その用語をほとんど無視できることを意味します（log（log ... log（n）...）によく似ています）。つまり、lg *（n）です。例：最小スパニングツリー（こちら）およびジョイントセットフォレストの構築。

また： Davenport-Scinzelシーケンス

Answer 2

元の「使用」アッカーマン関数の目的は、プリミティブな再帰的ではない関数、つまり、所定の上限を持つループのみを使用して計算できない関数があることを示すことでした。

アッカーマン関数はそのような関数であり、成長が速すぎて原始再帰的ではありません。

本当に実用的な用途があるとは思わない。それはあまりにも速く成長して有用ではない。妥当なスペースでa（4,3）を超える数値を明示的に表すことさえできません。

Answer 3

「理論上」という他の答え（wrang-wrangによる）に同意します。

実際には、Ackermanはあまり有用ではありません。実際には、遭遇する傾向のある唯一のアルゴリズムの複雑性には、1、N、N ^ 2、N ^ 3、およびlogNを掛けたものが含まれるからです。 （そして、logNは64を超えることはないので、とにかく実質的に一定の用語です。）

重要なのは、「実際に」、アルゴリズムの複雑さが「N倍」でなければ、実際の要因が支配するため、複雑さは気にしません。 （O（inverse-Ackermann）で実行する関数は、理論的にはO（logN）時間で実行する関数よりも優れていますが、実際には、実際のデータに対して2つの実際の実装を測定し、実際にパフォーマンスの良い方を選択します対照的に、複雑さの理論は、例えばN対N ^ 2について「実際問題」であり、アルゴリズムの複雑さの効果は実際には「現実世界」の効果を圧倒します。「N」は、実際には重要です。）