在我们大学的离散数学课程中,老师向他的学生展示了阿克曼函数,并让学生在纸上开发该函数。
除了作为递归优化的基准之外,阿克曼函数还有什么实际用途吗?
在我们大学的离散数学课程中,老师向他的学生展示了阿克曼函数,并让学生在纸上开发该函数。
除了作为递归优化的基准之外,阿克曼函数还有什么实际用途吗?
Ackermann 函数的原始“用途”是为了表明有些函数不是原始递归的,即不能通过仅使用具有预定上限的 for 循环来计算这些函数。
阿克曼函数就是这样一个函数,它增长得太快而不能成为原始递归。
我认为没有真正的实际用途,它增长太快而无用。您甚至无法在合理的空间内明确表示超出 a(4,3) 的数字。
我同意“理论上”的另一个答案(通过 wrang-wrang)。
在实践中,阿克曼并不太有用,因为在实践中,您往往会遇到的唯一算法复杂性涉及 1、N、N^2、N^3 以及每一个都乘以 logN。(而且由于 logN 永远不会超过 64,因此它实际上是一个常数项。)
关键是,“在实践中”,除非你的算法复杂度是“N 倍太大”,否则你不关心复杂性,因为现实世界的因素将占主导地位。(理论上,在 O(inverse-Ackermann) 中执行的函数比在 O(logN) 时间内执行的函数要好,但在实践中,您将根据实际数据测量两个实际实现,然后选择实际执行得更好的函数. 相比之下,复杂性理论确实“在实践中很重要”,例如 N 与 N^2,其中算法复杂性效应实际上压倒了任何“现实世界”效应。我发现“N”是在实践中重要的最小度量.)