有人能提供一个时间复杂度为O(n^5)的最小运行时间算法的例子吗?
关于复杂体积的O n5算法。
log n
个因素。此外,“n”指的是维度,而不是体积的复杂度。还要注意“凸”而不是“复杂”。该算法假定存在一个“分离预言机”,可以免费测试点是否在体内,如果不在,则给出一个分离平面...如果您对该领域不熟悉,您可能无法从“O(n^5)体积算法”的描述中推断出所有这些信息。 - Sumudu Fernandofor 1 to n
for 1 to n
for 1 to n
for 1 to n
for 1 to n
Do Something
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();
}
}
}
}
}
}
已经证明,10维空间中的凸包需要O(n^5)的时间复杂度(该证明适用于一般的d,表明在最坏情况下,凸包可以是O(n^floor(d/2)),如我所记得的)
O(n)
算法也是O(n^5)
。 - ypercubeᵀᴹ