复杂度时间 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+1)
n + ... + 1 = ─────────
                  2

证明:

n + ... + 1 = S

2*(n + ... + 1) = 2*S

n + n-1 + ... + 2   + 1 + 
1 + 2   + ... + n-1 + n = 2*S

n+1 + (n-1)+2 + ... + 2+(n-1) + 1+n = 2*S

n+1 + n+1 + ... + n+1 = 2*S

n*(n+1) = 2*S 

S = n*(n+1)/2 = (n*n+n)/2

但是：

 n*n     n*n + n          n*n + n*n
───── < ───────── = S < ──────────── = n*n
  2         2                 2

我们的总和低于（或等于 n=1）n*n（对于每个 n，但它足以对每个 n > n0 成立）。上面的假设是基于 n >= 1 => n*n >= n.
n*n 在 O(n²)

从 (1) 和 (2) => 我们的总和是 O(n²).

如果用下限(n*n/2)，也可以说是在Ω(n²) 然后在 Θ(n²).

正式定义

你也可以根据正式定义来证明，不过我觉得上面的解释更直观

f(n) = O(g(n)) means there are positive constants c and n0, such that 0 ≤ f(n) ≤ cg(n) for all n ≥ n0. The values of c and n0 must be fixed for the function f and must not depend on n.

f(n) = (n*n+n)/2
g(n) = n*n

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

0 ≤ (n*n+n)/2 ≤ 2*n*n
0 ≤ n*n+n ≤ 4*n*n
0 ≤ n ≤ 3*n*n

这显然适用于每个 n ≥ n0=1。

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

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

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

Complexity Time O(n) or O(n(n+1)/2)

algorithm

big-o

time-complexity