阿克曼函数的时间复杂性

Question

有人知道用big-O表示法计算ackermann函数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));
    }
}

Answer 1

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

Answer 2

我对这个函数了解不多，但仔细看，它似乎是伪多项式。也就是说，运行时取决于它的输入，在某些输入上可以是多项式时间，而在其他输入上则可以是非多项式时间。这可以用Cantor的对角化来证明

Answer 3

如果你感兴趣的只是Ack（3，n），那么它就是O（求幂）。Ack（3，n）＝2ⁿ⁺³-3。这可以用O（logn）运算来计算。

Answer 4

这主要是涉及巨大复杂性的第三种情况。。。它的形式是（（2^2）^2）^2等等…所以，通过检查你可以看到复杂性是2^（2^n）。。。这种复杂性比n^n要糟糕得多，所以我在其他地方读到阿克曼函数就像原始递归函数的上界，但我不完全确定。。。需要做更多的研究。。。