复杂度时间 O(n) 或 O(n(n+1)/2)

Question

循环 n 个项目（如数组）然后循环 (n-1) 然后循环 (n-2) 等等的算法的复杂性是多少 像：

Loop(int[] array) {
  for (int i=0; i<array.Length; i++) {
     //do some thing

  }
}
Main() {
   Loop({1, 2, 3, 4}); 
   Loop({1, 2, 3}); 
   Loop({1, 2}); 
   Loop({1}); 
//What the complexity of this code.
}

前面的程序的复杂度是多少？

Answer 1

公式：

\n\n

               n*(n+1)\nn + ... + 1 = \xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\n                  2\n

\n\n

证明：

\n\n

n + ... + 1 = S\n\n2*(n + ... + 1) = 2*S\n\nn + n-1 + ... + 2   + 1 + \n1 + 2   + ... + n-1 + n = 2*S\n\nn+1 + (n-1)+2 + ... + 2+(n-1) + 1+n = 2*S\n\nn+1 + n+1 + ... + n+1 = 2*S\n\nn*(n+1) = 2*S \n\nS = n*(n+1)/2 = (n*n+n)/2\n

\n\n

但：

\n\n

 n*n     n*n + n          n*n + n*n\n\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80 < \xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80 = S < \xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80 = n*n\n  2         2                 2\n

\n\n

\n
1. 我们的总和低于（或等于 n=1）n*n（对于每个n，但对于每个 都足够n > n0）。上述假设基于 n >= 1 => n*n >= n 的事实。
\n
2. n*n是O(n ² )
\n

\n\n

从 (1) 和 (2) => 我们的总和为O(n ² )。

\n\n

如果我们使用下限 ( n*n/2)，我们也可以说它在\xce\xa9(n ² )中，然后在\xce\x98(n ² )中。

\n\n\n\n

正式定义

\n\n

你也可以根据形式化定义来证明，但我发现上面的解释更直观。

\n\n

\n

f(n) = O(g(n)) 表示存在正常数 c 和 n0，使得 0 \xe2\x89\xa4 f(n) \xe2\x89\xa4 cg(n) 对于所有 n \xe2\ x89\xa5 n0。对于函数 f，c 和 n0 的值必须是固定的，并且不得依赖于 n。

\n

\n\n

f(n) = (n*n+n)/2\ng(n) = n*n\n

\n\n

只需选择n0 = 1和c = 2，您将得到：

\n\n

0 \xe2\x89\xa4 (n*n+n)/2 \xe2\x89\xa4 2*n*n\n0 \xe2\x89\xa4 n*n+n \xe2\x89\xa4 4*n*n\n0 \xe2\x89\xa4 n \xe2\x89\xa4 3*n*n\n

\n\n

这显然对每个 都是正确的n \xe2\x89\xa5 n0=1。

\n\n

一般来说，如果在选择常量时遇到问题，请使用更大的值。例如：n0=10、c=100。有时会更明显。

\n

Answer 2

假设你在循环中所做的事情是O(1)，这个的复杂度是O(n+(n-1)+(n-2)+...+1) = O(n(n+1)/2) = O(0.5n^2 + 0.5n) = O(n^2)

• 第一个=是由于算术级数和。
• 第二个=是由于打开乘法。
• 第三个=是因为给定一个内部多项式，O()您可以简单地将其替换为x^highest_power