时间复杂度（覃超）

Big O notation

• O(1): Constant Complexity: Constant 常数复杂度
• O(log n): Logarithmic Complexity: 对数复杂度
• O(n): Linear Complexity: 线性时间复杂度
• O(n^2): N square Complexity 平⽅方
• O(n^3): N square Complexity ⽴立⽅方
• O(2^n): Exponential Growth 指数
• O(n!): Factorial 阶乘

O(1)

int n = 1000;
System.out.println("Hey - your input is: " + n);
// 下面的无论输出几条，是O(1)复杂度
int n = 1000;
System.out.println("Hey - your input is: " + n); 
System.out.println("Hmm.. I'm doing more stuff with: " + n); 
System.out.println("And more: " + n);

O(n)

一般单层循环都为O（n)。

for (int = 1; i<=n; i++) {
    System.out.println(“Hey - I'm busy looking at: " + i);
}

O(n^2)

嵌套的2次循环都为n，所以整体循环了n*n次，即：n^2次。

for (int i = 1; i <= n; i++) { 
    for (int j = 1; j <=n; j++) {
        System.out.println("Hey - I'm busy looking at: " + i + " and " + j); 
    }
}

O(log(n))

for (int i = 1; i < n; i = i * 2) {
    System.out.println("Hey - I'm busy looking at: " + i);
}

O(k^n)

for (int i = 1; i <= Math.pow(2, n); i++){ 
    System.out.println("Hey - I'm busy looking at: " + i);
}

O(n!)

for (int i = 1; i <= factorial(n); i++){ 
    System.out.println("Hey - I'm busy looking at: " + i);
}

例子：一个求和的计算的优化

求和：1+2+3+4+….+n

// 时间复杂度为O（n)
// 1+2+3+....+n （总共累加n次）
sum =0;
for (i=1,i<=n,i++){
  sum = i+sum;
}
// 时间复杂度为O（1）
// 利用求和公式计算: n(n+1)/2
sum = n * (n+1)/2