有没有真正的O（n ^ n）算法？ [英] Are there any real O(n^n) algorithms?

问题描述

有没有时间复杂度为O（n ^ n）的真实算法，不仅仅是一个a头？

我可以创建这样的算法，例如计算O（n ^ n）/Θ（n ^ n）中的n ^ n：

  long n_to_the_power_of_m（int n，int m）{
 if（m == 0）返回1; 
长期总和= 0; 
 for（int i = 0; i< n; ++ i）
 sum + = n_to_the_power_of_m（n，m-1）; 
返还金额； 
} 
  

（需要4分钟以上的时间才能计算10 ^ 10）

还是其他方式：是否有没有比O（n ^ n）更好的解决方法？

解决方案

示例中的编码与深度优先搜索非常相似。因此，这就是一个答案。

没有任何特殊特征（例如可以优化出的重新收敛路径）的深度优先搜索算法应为n ^ n。 / p>

这实际上不是人为的示例。国际象棋程序使用相同的算法。每一个动作都需要考虑n个动作（即分支），然后搜索d个动作。这样就变成了O（n ^ d）

Is there any real Algorithm with a time complexity O(n^n), that isn't just a gimmick?

I can create such an Algorithm, like computing n^n in O(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;
}

(needs more than 4 minutes to compute 10^10)

Or other way around: Are there any Problems, which cannot be solved better than in O(n^n)?

解决方案

What you have coded in your example is very similar to a depth first search. So, that's one answer.

A depth first search algorithm without any special characteristics ( like re-convergent paths that can be optimized out ), should be n^n.

This is actually not a contrived example. Chess programs operate on the same algorithm. Each move there are n moves to consider ( i.e. branches ), and you search d moves deep. So that becomes O(n^d)

这篇关于有没有真正的O（n ^ n）算法？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！