11

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

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

4

3 に答える 3

17

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

また: Davenport-Scinzel シーケンス

于 2009-09-14T23:08:31.180 に答える
12

アッカーマン関数の本来の「用途」は、プリミティブな再帰的ではない関数があることを示すことでした。つまり、あらかじめ決められた上限を持つ for ループだけを使用して計算できない関数です。

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

本当に実用的な用途はないと思います。成長が速すぎて役に立ちません。適切なスペースで a(4,3) を超える数値を明示的に表すことさえできません。

于 2009-09-15T06:40:06.403 に答える
3

私は「理論的に」他の答え（wrang-wrangによる）に同意します。

実際には、Ackermanはあまり有用ではありません。実際には、遭遇する傾向のあるアルゴリズムの複雑さは、1、N、N ^ 2、N ^ 3、およびそれらのそれぞれにlogNを掛けたものだけだからです。（logNは64を超えることはないため、とにかく定数項になります。）

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

于 2009-09-14T23:28:07.823 に答える