该系列为本人的学习笔记，主要由本人整理书写而成。部分内容来自教材、视频课程等，不能保证完全原创性。
萌新的学习笔记，写错了恳请斧正。
# 复杂度
复杂度是衡量算法好坏的一种方式。一般分为时间复杂度和空间复杂度，分别用于衡量一个算法在运行时间长短和占据内存空间多少两方面的优劣。
一般我们考察复杂度就是找到相关的代数式，将常数全部忽略，将非最高次项全部忽略，在用括号括起来，前面写一个大 O。这就是复杂度的大 O 表示法。
比方说，对于代数式 3N^2+2N+4，我们只取 N^2；对于 2N+4M+1，我们只取 M+N。
（未知数的选用是随意的）
至于这个代数式如何找到，且看下方。
# 时间复杂度
时间复杂度的表达式就是算法执行基本语句的次数与未知量之间的代数关系（一般考虑最坏情况下的关系）。
比方说下面这一个函数，不含未知数，其基本语句的运行次数是常数次，时间复杂度就是 O (1)。
void function() | |
{ | |
for (int i = 0; i < 114514; ++i) | |
{ | |
print("%d\n", i); | |
} | |
} |
而下面这个函数含有未知数，循环中的代码段要运行 N 次，那么时间复杂度就是 O (n)。
void function(int n) | |
{ | |
for (int i = 0; i < n; ++i) | |
{ | |
print("%d\n", i); | |
} | |
} |
而下面这个函数虽然有两个循环，但是相互独立，一个运行 N 次，一个运行 2N 次，一共是 3N 次，舍去常数后，时间复杂度还是 O (N)。
void function(int n) | |
{ | |
for (int i = 0; i < n; ++i) | |
{ | |
print("%d\n", i); | |
} | |
for (int i = 0; i < 2n; ++i) | |
{ | |
print("%d\n", i); | |
} | |
} |
但是要注意两个未知数一样时才能合并，不然就还是要写成两个未知数的代数式。比方说下面这一段的时间复杂度为 O (M+N)。（如果说明 M 远大于 N 则可以省略 N；如果 MN 存在代数关系则需要计算）
void function(int a, int b) | |
{ | |
for (int i = 0; i < 3a; ++i) | |
{ | |
print("%d\n", i); | |
} | |
for (int i = 0; i < 4b; ++i) | |
{ | |
print("%d\n", i); | |
} | |
} |
而下面这一段函数的时间复杂度为 O (M^2+N)，因为两个未知数是独立的，舍去非最高次项时不能舍弃含有其他未知数的项。
void function(int a, int b) | |
{ | |
for (int i = 0; i < 3a; ++i) | |
{ | |
for (int j = 0; j < 5a; ++j) | |
{ | |
print("%d\n", i); | |
} | |
} | |
for (int i = 0; i < 4b; ++i) | |
{ | |
print("%d\n", i); | |
} | |
} |
再复杂一点，我们看看冒泡排序的时间复杂度，其结果为 O (n^2)：
void bubbleSort(int p[], int n) // 冒泡排序，并打印比较次数和移动次数 | |
{ | |
_Bool flag = false; | |
int cnt1 = 0; | |
int cnt2 = 0; | |
int swi = 0; | |
do | |
{ | |
flag = false; | |
for (int i = 0; i < n - 1; i++) | |
{ | |
if (p[i], p[i + 1]) | |
{ | |
swi = p[i + 1]; | |
p[i + 1] = p[i]; | |
p[i] = swi; | |
flag = true; | |
cnt2++; | |
} | |
cnt1++; | |
} | |
} while (flag); | |
printf("%d %d ", cnt1, cnt2); | |
} |
表达式也有可能含有其他数学运算，比方说二分搜素的时间复杂度就是 O (logN)（注意对数的底数省略不写）：
int bin_search(int arr[], int left, int right, int key) | |
{ | |
int i; | |
int j = 1; | |
do | |
{ | |
i = (right + left) / 2; | |
if (key > arr[i]) | |
left = i; | |
else | |
right = i; | |
} while (arr[i] != key); | |
return i; | |
} |
甚至更复杂的，有些表达式想要求出来需要较复杂的数列运算，包括但不限于使用等比数列求和公式、差比数列求和公式、裂项相消、配项......
# 空间复杂度
空间复杂度的表达式描述的是使用某算法所需要的 “额外” 空间开销与未知数的关系（同样是一般考虑最坏情况）。
首先，我们要注意这里的空间开销是算法额外产生的而不包括原本就开辟的空间。
比方说，下面这个函数用于将一个数组的数据复制到另一个数组，那么本身就存在的数组的空间当然不能算在算法的空间开销中，其额外开辟的空间只有变量 i，则空间复杂度为 O (1)。
void copyArr(int* arr1, int* arr2, int n) | |
{ | |
for (int i = 0; i < n; ++i) | |
{ | |
arr2[i] = arr1[i]; | |
} | |
} |
而如果我们写成这样，空间复杂度就变成 O (N) 了：
void copyArr(int* arr1, int* arr2, int n) | |
{ | |
int* arrTmp = (int*)malloc(n * sizeof(int)); | |
for (int i = 0; i < n; ++i) | |
{ | |
arrTmp[i] = arr1[i]; | |
arr2[i] = arrTmp[i]; | |
} | |
} |
空间复杂度也可以变的较为复杂，比方说求斐波那契数列的空间复杂度：
int Feb(int n) | |
{ | |
if (1 == n || 2 == n) | |
return 1; | |
else | |
return Feb(n - 1) + Feb(n - 2); | |
} |
想要算明白这个，需要对递归和函数栈帧（详见函数栈帧相关博客）有更深刻的理解。
由于递归不是一层一层进行的，所以其空间复杂度并不是总共开辟的栈帧空间的数量。
递归是一条路走到底再返回走其他路的，所以空间复杂度等于其路径深度，也就是 O (N)。
（这里学过深度优先搜素 dfs 就清楚了）
# 通过复杂度衡量算法好坏
一般我们认为，对于一个算法而言，其优劣可以通过未知数趋于无穷时的复杂度体现。而一般我们可以通过下面的不等式链比较复杂度：
