目录
算法背景 background
核心：Algorithms + Data Structures = Programs
-》高性能的代码 = 相应速度快的代码。需要初级程序员了解算法，灵活地运用算法。
-》发明设计一款算法：要去推导证明算法的可行性。
数据结构是为算法服务的，而算法又需要作用在特定的数据结构上。
-》谁的算法快，谁的算法更优！！
如果两种算法实现的速度差不多，那我们还可以去评价算法所占用的空间。
时间复杂度：执行当前算法所消耗的时间。--》快
空间复杂度：执行当前算法所消耗的内存空间。--》省
1. 时间复杂度 Time Complexity
时间复杂度 time complexity：全称为算法的渐进时间复杂度，表示执行当前算法的最高运算次数，记作T(n)=O(f(n))，表示算法的执行时间与数据规模n之间的增长关系。
核心：分析算法时间复杂度的关键在于分析出代码循环了多少次！
Note：时间复杂度反映的只是一个趋势，也就是随着n的变化，算法执行时间的也是会变化的。
1.1 时间复杂度分类
1.1.1 O(1) 常数阶
本质：复杂度与数据规模n无关！
public static void print(int n){
int a = 1;
int b = 2;
int c = 3;
int sum = a + b + c;
System.out.println(sum);
}1.1.2 O(n) 线性阶
对应：单层for循环
public static void print1(int n){
int a = 0; // 复杂度：T
for (int i=0;i<n;i++){
System.out.println(i); // 复杂度：n*T
}
}
假设每一行代码的执行时间是T，那上段代码的执行时间T(n)= T+n*T=(n+1)T.
->算法时间复杂度 Rule 1: 常量可以被忽略。
所以，T(n) = nT = O(n).
1.1.3 O(n^2) 平方阶
双层循环平方阶；
三层循环立方阶；
K层循环就是K次立方阶。
1.1.4 O(logn) 对数阶
对应：while 循环
e.g. 二分查找，二叉树问题
public static void print2(int n){
int i=1;
while (i <= n) {
i = i * 2;
}
}
分析算法时间复杂度的关键在于分析出while循环了多少次。
1->2->4->8...
，只要能得到x的值，就得到了循环次数。
同理， ，不管底数是多少，最终都可以转换为以2为底的对数阶 =》
=》算法时间复杂度 Rule 2: 当循环中下标以指定倍数形式衰减，那么这就是一个对数阶。
1.1.5 O(nlogn) 线性对数阶
时间复杂度 = 代码执行次数！
for (int j=1;j<=n;j++){
int i=1; // 时间复杂度 O(n)
while (i <= n) {
i = i * 2; // 时间复杂度 O(logn)
}
}
嵌套代码的时间复杂度 = 单独的嵌套内循环 * 单独的嵌套外循环
= 嵌套内外循环时间复杂度之和
1.1.6 O(2^n) 指数阶
def exponential(n: int) -> int:
"""指数阶（循环实现）"""
count = 0
base = 1
# 细胞每轮一分为二，形成数列 1, 2, 4, 8, ..., 2^(n-1)
for _ in range(n):
for _ in range(base):
count += 1
base *= 2
# count = 1 + 2 + 4 + 8 + .. + 2^(n-1) = 2^n - 1
return count单独的嵌套内循环次数无法计算
无法利用乘积求时间复杂度，只能用加法了
嵌套外循环时间复杂度 O(n)
base：1, 2, 4, 8, 2^(n-1)
嵌套内循环次数：等比数列求和公式
1.1.7 O(n!) 阶乘阶
def factorial_recur(n: int) -> int:
"""阶乘阶（递归实现）"""
if n == 0:
return 1
count = 0
# 从 1 个分裂出 n 个
for _ in range(n):
count += factorial_recur(n - 1)
return count1.1.8 时间复杂度分类
最好时间复杂度、最坏时间复杂度、平均时间复杂度
1.2 时间复杂度 Rules
- 只要是常数级别，不论n多大，代码效率都是一样的。
- 忽略常量、低次幂和高次幂系数。
嵌套代码的时间复杂度
= 单独的嵌套内循环 * 单独的嵌套外循环
= 嵌套内外循环时间复杂度之和
在同一个算法中，存在明确大小关系的，可以直接取最大值作为这个算法的复杂度。
多项式时间复杂度关系：
指数时间复杂度关系：
1.3 时间复杂度计算流程
Note：只有可运行的语句才会增加时间复杂度，除了循环外，其他可执行语句的时间复杂读都是O(1)，可以被忽略。
(1) 计算出基本操作的执行次数T(n). 计算算法中每条语句的执行次数；在做算法分析时，一般默认为考虑最坏的情况，而不是考虑循环break or continue情况。
(2) 计算出T(n)的数量级。忽略常量、低次幂和高次幂系数。
(3) 用O表示时间复杂度。只保留最高项
for（i=1;i<=n;++i）
{
for(j=1;j<=n;++j)
{
c[ i ][ j ]=0; //该步骤属于基本操作 执行次数：n^2
for(k=1;k<=n;++k)
c[ i ][ j ]+=a[ i ][ k ]*b[ k ][ j ]; //该步骤属于基本操作 执行次数：n^3
}
} 第一步计算基本语句执行次数：T（n）= n^2+n^3；
第二步T（n）的同数量级，我们可以确定 n^3为T(n) 的同数量级；
第三步用大O表示时间复杂度：T(n) =O(n^3)。
2. 空间复杂度 Space Complexity
空间复杂度 space complexity：全称为算法的渐进空间复杂度，表示执行当前算法所消耗的内存空间。是指一个算法在运行过程中临时占用存储空间大小的度量，记作S(n)=O(f(n))，用来表示算法的存储空间雨数据规模n之间的增长关系。
核心：以最差的输入数据为准；以算法运行中的峰值内存为准。
- 定义一个常数变量，与n无关，它的空间复杂度为O(1).
- 定义一个数组，数组长度为n，这个数组需要的空间复杂度为O(n)，因为它的空间随着n变化而变化。
- 二维数组，空间复杂度
参考
https://www.cnblogs.com/lonely-wolf/p/15674526.html