阿克曼函数的时间复杂度

Question

有人知道计算阿克曼函数ack(m,n)的时间复杂度是大O符号表示法中的哪个复杂度类别吗？或者只计算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));
    }

}

- Thorben

---

使用您的代码计算ack(3, n)将进行的递归调用次数是指数级的 - 您可以从http://oeis.org/A074877计算它将进行的确切调用次数。 - Dogbert

Answer 1

随着输入长度或时间复杂度的增加，最坏情况计算时间的渐近极限无法定义为mu递归函数，至少不能仅使用典型的大O符号表示法。而且这仅适用于那些类似于我们的主题，是“总体”的mu递归函数。

- ARi

---

Ackermann函数不能通过for next循环进行编程，循环限制为参数的任何原始递归函数。您将不得不坚持使用while循环，并且无法确定迭代次数。 - ARi

Answer 2

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

- sosostris

Answer 3

我对这个函数不是很了解，但快速查看它，似乎是伪多项式。也就是说，运行时间取决于输入，并且在某些输入上可以是多项式时间，而在其他情况下则不是。这可以使用Cantor的对角线法证明。

- Chevy787

---

好的。那它的名称是什么？复杂度类别是伪多项式吗？ - Thorben

我会说那是复杂度类。同时请查看http://arstechnica.com/civis/viewtopic.php?f=20&t=865597。 - Chevy787

听起来不错。尽管我已经了解了一些关于ELEMENTARY的信息http://en.wikipedia.org/wiki/ELEMENTARY，我认为它的补集（NONELEMENTARY）也可以描述这个函数的特征。你认为这样说对吗？ - Thorben

我真的不确定，但我认为这是有可能的。希望其他人能够澄清事情。 - Chevy787

好的，谢谢。在那之前，我决定将其简单地分类为非简单递归，就像它的目的一样。 - Thorben

据我所知，第一个伪多项式意味着算法的运行时间是输入值的多项式（而不是其长度）。因此，给出的定义是错误的。至于阿克曼函数，据我所知，它比多项式或伪多项式要糟糕得多！即使结果可以立即计算，由于即使对于相对较小的输入，生成的数字也非常大，仅仅将结果写成二进制形式就需要比任何合理的复杂度类更长的时间。 - D.F.F

Answer 4

如果您只关心Ack(3,n)，那么它的时间复杂度为O(exponentiation)。Ack(3,n) = 2ⁿ⁺³-3。这可以用O(logn)的操作计算出来。

- SomeWittyUsername

---

没错，但我把它用作基准，所以我采用了Péter的标准形式。我添加了一个代码示例。 - Thorben