最近在查漏补缺看看计算机学科最重要的课程之一，课程讲得很好。
课程地址
算法时间复杂度
大$O$记号：算法的最差情况时间复杂度
大$Ω$记号：最好情况
大$Θ$记号：当算法最差情况与最好情况属同一复杂度时，则可用该记号。$Θ(n) = Ω(n) = O(n)$
- 常见时间复杂度：
| 名称 | 记号 | 分类 |
|---|---|---|
| 常数复杂度 | $O(1)$ | 高效解 |
| 对数复杂度 | $O(log_{c}(n)) = O(log_{c}(2)) * O(log_{2}(n)) = O(logn)$ | 高效解 |
| 多项式复杂度 | $O(n^c) 丨 c\geq 1$ | 有效解 |
| 指数复杂度 | $O(c^n) = O(2^n)$ | 难解 |
时间复杂度比较：
$O(log^*n) < O(loglogn) < O(logn) < O(\sqrt{n}) < O(n) < O(nlogn)$
级数次操作与其时间复杂度：
幂方级数：$1^d + 2^d +\cdots + n^d = O(n^{d+1})$
几何级数：$a^0 + a^1 + a^2 + \cdots + a^n = \frac{a^{n+1} + 1}{a - 1} = O(2^n)$
收敛级数：$O(1)$
*调和级数：$1 + \frac{1}{2} + \frac{1}{3} + \cdots + \frac{1}{n} \approx ln(n) + γ = O(logn)$
*对数级数：$log1 + log2 + \cdots + logn = log(n!) \leq log(n^n) = O(nlogn)$
- 分摊复杂度：操作m次，m足够大，得到时间T，由T/m进行复杂度分析。
- 平均复杂度：输入实例符合某种概率分布，对各实例所得到的T进行加权求和得到的复杂度。
递归
- 递归基（base case of recursion）：递归终止条件与值，如 $fibonacci(0) = 0, fibonacci(1) = 1$。
- 线性递归（Linear recursion）：减而治之，每深入一层，待求解问题的规模都缩减一个常数，并只自调一次，与分而治之区别于每个递归实例上层仅有一个实例，与尾递归区别于最后一步不是递归操作。
ADT：Abstract Data Type 抽象数据类型，就是数据类型的接口文档
DS：Data Structure 数据结构，具体语言根据ADT实现的数据类型封装。
向量
- 上溢：Overflow
- 下溢：Underflow，指装载因子过小，$λ = size / capacity << 50\%$
为何Vector动态扩容采用的是乘法形式而不是加法？
假设向量初始容量为1，插入$n$个元素
加法：每插入$c$个元素进行一次扩容，第$x$次扩容需要时间复杂度为$O(xc)$，得：
$T(n) = c + 2c + 3c + \cdots + \frac{n-1}{c}*c $ 为算数级数
分摊复杂度：$T(n) / n = O(n)$
$ λ \approx 100\%$
乘法：每次乘2，第$x$次为$O(2^x)$，令$n = 2^c$
$T(n) = 2 + 4 + 8 \cdots + 2^c$ 为几何级数 $O(2^{log_{2}n}) = O(n)$
分摊复杂度：$T(n) / n = O(1)$
$λ \approx 50\%$
等于用空间换时间。