O(n.m^2)算法的运行时间

Question

我想知道，因为我在网上找不到任何信息，像O(n * m^2)、O(n * k)或O(n + k)这样的算法应该如何分析？

只有n算吗？

其他条款是多余的吗？

所以O(n * m^2)实际上是O(n)

Answer 1

不，这里的k项和m项不是多余的，它们确实有一个有效的存在，对于计算时间复杂性是必不可少的。它们被封装在一起，为代码提供了一个具体的复杂性。

在代码中，术语n和k似乎是相互独立的，但它们共同决定了算法的复杂性。

比方说，如果你必须迭代一个n-元素的循环，而在中间又有一个k-迭代循环，那么总的复杂度就变成O(nk)。

order O(nk)的复杂性，您不能在这里转储/丢弃k。

for(i=0;i<n;i++)
for(j=0;j<k;j++)
// do something

order O(n+k)的复杂性，您不能在这里转储/丢弃k。

for(i=0;i<n;i++)
// do something
for(j=0;j<k;j++)
// do something

O(nm^2)的复杂性，您不能在这里转储/丢弃m。

for(i=0;i<n;i++)
for(j=0;j<m;j++)
for(k=0;k<m;k++)
// do something

最后一个问题的答案--所以O(n.m^2)实际上是O(n)？

不，O(nm^2)复杂度不能进一步降低到O(n)，因为这意味着m没有任何意义，但实际上并非如此。

Answer 2

形式: O(f(n))是满足下列条件的所有函数T(n)的集合：

存在正常数c和N，使得对于所有n个>= N，

                          T(n) <= c f(n)   

这里有一些例子，说明了在什么时候，为什么不是n个因素。

1,000,000 n在O(n)中。证明:集合c= 1,000,000，N= 0。

大-哦符号不关心(大多数)常量因素。我们通常忽略常量；没有必要写O(2n)，因为O(2n) = O(n)。(2没有错，只是没有必要。)

2 n在O(n^3)中。那是正方形的。证明:设置c= 1，N= 1。大-欧表示法可能有误导性。仅仅因为一个算法的运行时间在O(n^3)中，并不意味着它是慢的；它也可能在O(n)中。大-噢符号只给我们一个函数的上界。

3 n^3 + n^2 +n在O(n^3)中。证明:设置c= 3，N= 1。大-欧表示法通常只用于表示函数中的支配项(最大和最令人不快的)。当n真的很大时，其他的术语就变得无关紧要了。

这些都是不可概括的，每一种情况都可能不同。这就是问题的答案：“只算n吗?其他术语是多余的吗？”

Answer 3

虽然已经有一个被接受的答案，但我仍然想提供以下输入：

O(n * m^2) : Can be viewed as n*m*m and assuming that the bounds for n and m are similar then the complexity would be O(n^3).

同样-

O(n * k) : Would be O(n^2) (with the bounds for n and k being similar)

还有-

O(n + k) : Would be O(n) (again, with the bounds for n and k being similar).

PS:在尝试结束之前，最好不要假设变量之间的相似性，并且首先了解变量之间的关系(例如: m=n/2；k=2n)。