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 回答