算法运行时间为O(nm ^ 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).

订单O(nk)的复杂性,你不能在这里转储/丢弃k.

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

订单O(n + k)的复杂性,你不能在这里转储/丢弃k.

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

订单O(nm ^ 2)的复杂性,你不能在这里转储/丢弃.

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

回答最后一个问题---所以O(nm ^ 2)实际上是O(n)？

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