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)。

阶数复杂度 O(nk)，你不能在此处 dump/discard k。

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

阶数复杂度 O(n+k)，你不能在这里 dump/discard k。

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

阶数复杂度 O(nm^2)，你不能在这里 dump/discard m。

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

Answer to the last question---So O(n.m^2) is actually 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] 1,000,000 n 在 O(n) 中。证明：设c = 1,000,000, N = 0.

Big-Oh 表示法不关心（大多数）常数因子。我们通常会忽略常量；没必要写 O(2n)，因为 O(2n) = O(n)。（2 没有错，只是没必要。）

[2] n 在 O(n^3) 中。 [那是 n 的立方]。证明：设c=1，N=1。 Big-Oh 表示法可能会产生误导。仅仅因为算法的运行时间在 O(n^3) 中并不意味着它很慢；它也可能在 O(n) 中。 Big-Oh 符号只给我们一个函数的上限。

[3] n^3 + n^2 + n 在 O(n^3) 中。证明：设c=3，N=1。 Big-Oh 表示法通常仅用于指示主导（最大和最令人不快的）函数中的术语。其他条款成为当 n 很大时微不足道。

这些都不是一概而论的，每个案例都可能不同。这就是问题的答案："Does only the n count? The other terms are superfluous?"

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）试图得出结论。

Algorithm Running Time for O(n.m^2)