总览
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
