complexity-theory - 阿克曼函数的时间复杂度

Question

有人知道用 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));
    }

}

Answer 1

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