算法的时间复杂度 - 大O

Question

我想知道这个算法的复杂度，我在 O(mn) 和 O(mn + n) 之间感到困惑：

i = 1; j=1;
while(j <= n)
{
  if(i <= m) i++;
  else
     {
       j++; i=1;
     }
}

感谢您的帮助！

Answer 1

设 f(m, n) 是给定 m[ 的输入时算法所采取的步数=91=] 和 n.

当我们说 f(m, n) 是 O(mn) 或者是“在 mn 的顺序上”，我们并不是说有两个函数具有相等的值。这是shorthand的说法：

• 有一点m₀,n₀ 和一些常量 C 超出 f(m, n) 总是小于或等于 Cmn。 “超越”是指 m₀ ≤ m 和 n₀ ≤ n.

假设算法需要 mn+n 步，所以 f(m, n) = mn+n.

考虑 m₀ = 1, n₀ = 0, C = 2. 则证明m₀ ≤ m 和 n₀ ≤ n 意味着 f(m, n) ≤ 2mn:

• f(m, n) = mn+n .
• 因为 1 ≤ m, mn+n ≤ mn + mn.
• mn + mn = 2mn.
• So f(m, n) ≤ 2mn.

因此 f(m, n) = mn+ n 是 O(mn); f(m, n) 是“在 mn 的数量级上。”