有没有真正的O(n ^ n)算法？

Question

有没有时间复杂度为O(n ^ n)的真实算法,这不仅仅是一个噱头？

我可以创建这样的算法,比如在O(n ^ n)/Θ(n ^ n)中计算n ^ n:

long n_to_the_power_of_m(int n, int m) {
    if(m == 0) return 1;
    long sum = 0;
    for(int i = 0; i < n; ++i)
        sum += n_to_the_power_of_m(n, m-1);
    return sum;
}

(计算10 ^ 10需要4分钟以上)

或者其他方式:是否存在任何问题,这些问题不能比O(n ^ n)更好地解决？

Answer 1

您在示例中编码的内容与深度优先搜索非常相似.所以,这是一个答案.

没有任何特殊特征的深度优先搜索算法(如可以优化的重新聚合路径)应该是n ^ n.

这实际上不是一个人为的例子.国际象棋程序在相同的算法上运行.每次移动都有n个动作要考虑(即分支),你搜索d移动深.这就变成了O(n ^ d)

Answer 2

有计算(例如,tetration),其中输出大小是O(n ⁿ).在时间复杂度小于O(n ⁿ)的情况下计算它们有点困难.

Answer 3

根据维基百科,有一些双指数时间问题O(2 ^{2 poly(n)})比O(n ⁿ)更复杂,例如" Presburger算法的决策程序"(O(2 ^{2 cn}))和"计算"一个Gröbner基 "(在最坏的情况下O(2 ^{2 N/10})