logo标签列表

一个具有O(n^5)复杂度的算法的例子是什么？

algorithmtime-complexity
4

有人能提供一个时间复杂度为O(n^5)的最小运行时间算法的例子吗？

2
顺便说一下，任何线性的 O(n) 算法也是 O(n^5)。 - ypercubeᵀᴹ
ypercube是对的，人们常常混淆大O符号和大Θ符号，这可能是他所指的。 - Alex Lo
6个回答
8
+1 个好例子。你是之前就知道还是刚刚 Google 的？ - ypercubeᵀᴹ
3
"plead the fifth?" :) 从这个问题中我很好奇，恰巧发现了一个不错的问题。 翻译： "plead the fifth?" :) 这个问题让我很好奇，碰巧发现了一个不错的问题。 - Brandon Frohbieter
我想你可以说3SAT或旅行商问题至少也是O(n^5) :) 无论如何，干得好... - dana
1
请注意，这是O(n^5)级别的算法，这意味着它们忽略了log n个因素。此外，“n”指的是维度，而不是体积的复杂度。还要注意“凸”而不是“复杂”。该算法假定存在一个“分离预言机”，可以免费测试点是否在体内，如果不在，则给出一个分离平面...如果您对该领域不熟悉，您可能无法从“O(n^5)体积算法”的描述中推断出所有这些信息。 - Sumudu Fernando
4
for 1 to n
 for 1 to n
  for 1 to n
   for 1 to n
    for 1 to n
     Do Something
不，n 应该是输入的大小。而且它应该是最小的。 - Adibe7
所以，将for循环更改为"foreach n"。Do Something可以返回5宽元组，这是一种最简单的方法，用于返回n个对象集的所有5宽元组。 - Alex Lo
4
void N5(int n)
{
    for( int n1 = 0; n1 < n; n1++ )
    {
        for( int n2 = 0; n2 < n; n2++ )
        {
            for( int n3 = 0; n3 < n; n3++ )
            {
                for( int n4 = 0; n4 < n; n4++ )
                {
                    for( int n5 = 0; n5 < n; n5++ )
                    {
                        DoSomething();
                    }
                }
            }
        }
    }
}
3
1

已经证明，10维空间中的凸包需要O(n^5)的时间复杂度（该证明适用于一般的d，表明在最坏情况下，凸包可以是O(n^floor(d/2))，如我所记得的）

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接