ackermann函数的时间复杂度

Question

有人知道用big-O表示法计算ackermann函数ack(m,n)的时间复杂度或者它属于哪个复杂类？Just 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

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