有没有真正的O（n ^ n）算法？

| 是否有任何时间复杂度为O（n ^ n）的真实算法，而不仅仅是Algorithm头？ 我可以创建这样的算法，就像在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;
}
（需要4分钟以上才能计算10 ^ 10） 还是其他方式：是否有没有比O（n ^ n）更好地解决的问题？     
2020-05-26 6 条评论
分享

没有找到相关结果

    已邀请:

    队辅坟阮阶

            您在示例中编写的代码与深度优先搜索非常相似。所以，这就是一个答案。 没有任何特殊特征（例如可以优化出的重新收敛路径）的深度优先搜索算法应为n ^ n。 这实际上不是人为的例子。国际象棋程序使用相同的算法。每一个动作都需要考虑n个动作（即分支），然后搜索d个动作。这样就变成了O（n ^ d）     
    2020-05-26 0 0
    分享

    填盖

            在某些计算（例如，四方）中，输出大小为O（nn）。以小于O（nn）的时间复杂度来计算它们是很困难的。     
    2020-05-26 0 0
    分享

    翁茄口霉氖

            根据Wikipedia的说法，存在一些双指数时间问题O（22poly（n）），比O（nn）更复杂，例如\“ Presburger算术的决策程序\”（O（22cn））和\“计算Gröbner基\”（在最坏的情况下为O（22n / 10）     
    2020-05-26 0 0
    分享

    疮痪徘弦漏

            存在许多本质上是O（n！）的优化问题，即数据压缩。通用的算法都需要一种或另一种作弊方式（许多依赖于启发式算法），但不能确保以这种方式找到了理想的结果。即在压缩PNG图像期间选择最佳行滤波器是一个相对容易理解的问题。 另一个例子是破坏加密的算法，该算法可能甚至比O（n！）更糟。     
    2020-05-26 0 0
    分享

    盟犯涩沟都

            该程序描述（终止）图灵机，并返回终止所需的步骤数。这是一个相对简单的程序，可以模拟图灵机并计算步数。 该程序的复杂性没有可计算的上限（并且特别是比任何可计算的函数增长更快），因此当然比O（n ^ n）增长更快。 输入大小为n的最坏情况下的运行时间是BB（n），此后未知以0、1、4、6、13开始的Busy Beaver序列（尽管存在下限-例如接下来的两个值分别至少为47176870和7.412×10 ^ 36534），并且对于足够大的n而言是不可计算的。     
    2020-05-26 0 0
    分享
    为什么被折叠? 0 个回复被折叠

    要回复问题请先登录或注册

    或代码 OrCode.com 备案号：粤ICP备15020848号-1
    Escape time: 0.049855947494507