8

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

谢谢。

代码片段：

public class Ackermann {

    public static int ackermann(int n, int m) {

        if (n == 0)
            return m + 1;
        else if (m == 0)
            return ackermann(n - 1, 1);
        else
            return ackermann(n - 1, ackermann(n, m - 1));
    }

}
4

4 回答 4

3

最坏情况计算时间的渐近限制，表示为输入长度或时间复杂度的函数：不能为 mu 递归函数定义，至少在不参考与典型大 oh 符号非常不同的另一个 mu 递归函数的情况下不能定义。这仅适用于那些像我们的主题一样“完全”的 mu 递归函数。

于 2015-11-01T17:18:34.990 回答
2

如果你只对 Ack(3,n) 感兴趣，那就是 O(exponentiation)。Ack(3,n) = 2 n+3 -3。这可以通过 O(logn) 操作来计算。

于 2013-06-29T06:24:24.990 回答
2

这个函数我不是太了解，但是快速看了一下，好像是伪多项式。也就是说，运行时间取决于它的输入，并且在某些输入上可以是多项式时间，而在其他输入上可以是非多项式时间。这可以使用康托尔对角化来证明

于 2013-06-28T14:53:37.980 回答
2

它主要是第三种情况，涉及大量复杂性......它的形式是 (((2^2)^2)^2)^2 等等......所以，通过检查你可以看到复杂性是 2^(2^n) ...这种复杂性比 n^n 差得多，所以我在其他地方读到阿克曼的函数就像原始递归函数的上限，但我对此并不完全确定......需要做更多的研究......

于 2016-11-18T13:55:16.890 回答