总览

image.png image.png

1. 时间复杂度 空间复杂度

1.1 Big O notation

-- What is Big O? --
: Constant Complexity: Constant 常数复杂度
: Logarithmic Complexity: 对数复杂度
: Linear Complexity: 线性时间复杂度
: N square Complexity 平方
: N square Complexity 立⽅
: Exponential Growth 指数
: Factorial 阶乘

常数复杂度

int n = 1000;
System.out.println("Hey - your input is: " + n);

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

线性时间复杂度

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

平方

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);
}

指数

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

阶乘

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

时间复杂度对比

1.2 To calculate: 1 + 2 + 3 + … + n

• 硬计算：1 + 2 + 3 + … + n (总共累加n次）
  y = 0
  for i = 1 to n:
  y = i + y
• 求和公式：n(n+1)/2
  y = n * (n + 1) / 2

1.3 What if recursion ?

• Fibonacci array: 1, 1, 2, 3, 5, 8, 13, 21, 34, …
  F(n) = F(n-1) + F(n-2) :

def fib(n):
 if n == 0 or n == 1:
   return n
 return fib(n - 1) + fib(n - 2)

Fib(6)

2. Master Theorem 主定律

需要掌握的常见算法复杂度

参考：
https://en.wikipedia.org/wiki/Master_theorem_(analysis_of_algorithms)
https://zh.wikipedia.org/wiki/%E4%B8%BB%E5%AE%9A%E7%90%86