11

在我们大学的离散数学课程中，老师向他的学生展示了阿克曼函数，并让学生在纸上开发该函数。

除了作为递归优化的基准之外，阿克曼函数还有什么实际用途吗？

4

3 回答 3

17

是的。（逆）阿克曼函数出现在算法的复杂性分析中。当它出现时，这意味着您几乎可以忽略该术语，因为它增长如此缓慢（很像 log(log ... log(n)...)），即 lg*(n)。例如：最小生成树（也在这里）和不相交集森林建设。

另外：Davenport-Scinzel 序列

于 2009-09-14T23:08:31.180 回答
12

Ackermann 函数的原始“用途”是为了表明有些函数不是原始递归的，即不能通过仅使用具有预定上限的 for 循环来计算这些函数。

阿克曼函数就是这样一个函数，它增长得太快而不能成为原始递归。

我认为没有真正的实际用途，它增长太快而无用。您甚至无法在合理的空间内明确表示超出 a(4,3) 的数字。

于 2009-09-15T06:40:06.403 回答
3

我同意“理论上”的另一个答案（通过 wrang-wrang）。

在实践中，阿克曼并不太有用，因为在实践中，您往往会遇到的唯一算法复杂性涉及 1、N、N^2、N^3 以及每一个都乘以 logN。（而且由于 logN 永远不会超过 64，因此它实际上是一个常数项。）

关键是，“在实践中”，除非你的算法复杂度是“N 倍太大”，否则你不关心复杂性，因为现实世界的因素将占主导地位。（理论上，在 O(inverse-Ackermann) 中执行的函数比在 O(logN) 时间内执行的函数要好，但在实践中，您将根据实际数据测量两个实际实现，然后选择实际执行得更好的函数. 相比之下，复杂性理论确实“在实践中很重要”，例如 N 与 N^2，其中算法复杂性效应实际上压倒了任何“现实世界”效应。我发现“N”是在实践中重要的最小度量.)

于 2009-09-14T23:28:07.823 回答