问题标签 [ackermann]

有谁知道以 big-O 表示法计算阿克曼函数 ack(m,n) 的时间复杂度或它属于哪个复杂度类？只需 Ack(3, n) 也足够了。我在某处读到它是非小学的？

谢谢。

代码片段：

用 Java 编写的标准阿克曼公式：

我一直在想 - 有没有更快的版本来实现这个？我在想也许有通过使用累加器或循环。

这是 7 个月前的一个老问题，当时堆栈溢出者同意 Haskell 计算 Ackermann 函数的效率低下是由于编译器错误造成的。

Ackermann 使用 Haskell/GHC 效率很低

7个月后，这似乎是固定的。似乎 ack 使用线性内存运行，但运行速度非常慢。

我只是要求对此有任何见解。更详细的将获得投票。请记住，我是函数式编程的新手，即使是关于尾递归与常规递归的简单评论也会受到赞赏和支持。

阿克曼函数已尝试通过以下代码实现

我想做一个返回两个值的函数。第一个应该是ackerman函数的输出，第二个应该是函数被调用的次数。

我已经制作了 Ack 功能：

我尝试进行全局计数并将其添加到 if 和 elifs 之前并返回它的答案：

这显然是错误的。每次 m = 0 时它都会返回计数，这将是一个元组。

我怎样才能使它返回（例如）ack（3,4）的答案列表，它应该是125，以及它必须调用ack（m，n）的次数。所以如果我调用 ack(1.0,0.0) 它应该返回 [2.0, 2]。我需要一个列表，因为我需要用这个总和进行一些计算。

我需要知道的原因是因为老师给了我们一个任务，我完全被困住了。

作为实验的一部分，我想看看在有和没有缓存/记忆的情况下计算Ack(0,0)需要多长时间。Ack(4,19)但是我一直遇到一个简单的绊脚石……我的堆栈一直在溢出。

这是我的代码：

我使用 Scala 和 SBT 插件在 IntelliJ Idea 13.1.3 中运行 Scala 2.11.1。

有什么办法可以避免在 Ack(3, 11) 附近发生堆栈溢出吗？

我已经尝试添加javacOptions += "-Xmx2G"到我的 build.sbt 中，但这似乎使问题变得更糟。

当输入值太高时，我试图让我的程序输出错误代码，但我只能让它在终端窗口中显示错误消息，而不是在方法返回中。这是代码：

我已经为 Ackermann 函数编写了一个非递归解决方案，它似乎工作得很好，并且比常见的递归解决方案工作得更快。所以我很困惑为什么它是一个非原始递归函数，如果它可以迭代解决？谁能告诉我，如果我误解了原始递归函数是什么，或者我应该与谁讨论这个问题以获得答案？

下面是Java代码：

这是我不断收到的错误：

每当我为第一个数字输入 -1 为第二个数字输入 -1 时，这种情况就会发生很多次。我知道它与 while 循环有关，并且尝试了很多方法来修复它，但想不出更好的方法来解决它。

如何使用 Raptor 流程图创建阿克曼函数？可以做到吗？我有一个大致的想法，但我不知道如何编写函数 2 或 3 a(m-1,1) 或 a(m-1, a(m,n-1)。