1. 算法基础
算法（Algorithm）是对特定问题求解步骤的一种描述，它是指令的有限序列，其中每条指令表示一个或多个操作。
算法的五个重要特性
| 特性 | 说明 |
|---|---|
| 有穷性 | 一个算法必须总是在执行有穷步之后结束，且每一步都可在有穷时间内完成 |
| 确定性 | 算法中每条指令必须有确切的含义，不会产生二义性 |
| 可行性 | 算法中描述的操作都可以通过已经实现的基本运算执行有限次来实现 |
| 输入 | 一个算法有零个或多个输入 |
| 输出 | 一个算法有一个或多个输出 |
算法设计的要求
- 正确性：算法应满足具体问题的需求
- 可读性：算法应易于阅读和理解
- 健壮性：当输入数据非法时，算法能适当地做出反应或进行处理
- 效率与低存储量需求：效率指算法执行的时间，存储量需求指算法执行过程中所需的最大存储空间
2. 时间复杂度与空间复杂度
2.1 渐进符号
大O表示法（O）
定义：若存在正常数 $c$ 和 $n_0$，使得当 $n \geq n_0$ 时，$T(n) \leq c \cdot f(n)$，则记为 $T(n) = O(f(n))$。
大O表示法表示算法运行时间的上界。
大Ω表示法（Ω）
定义：若存在正常数 $c$ 和 $n_0$，使得当 $n \geq n_0$ 时，$T(n) \geq c \cdot f(n)$，则记为 $T(n) = \Omega(f(n))$。
大Ω表示法表示算法运行时间的下界。
大Θ表示法（Θ）
定义：若 $T(n) = O(f(n))$ 且 $T(n) = \Omega(f(n))$，则记为 $T(n) = \Theta(f(n))$。
大Θ表示法表示算法运行时间的确界。
2.2 复杂度计算规则
加法规则
多项相加，保留最高阶项，并将系数化为1。
$$T(n) = O(n^2) + O(n) + O(1) = O(n^2)$$
乘法规则
多项相乘都保留，并将系数化为1。
$$T(n) = O(n) \times O(n) = O(n^2)$$
混合规则
小括号 → 再乘法规则 → 最后加法规则
2.3 常见时间复杂度
| 复杂度 | 名称 | 说明 |
|---|---|---|
| $O(1)$ | 常数阶 | 与问题规模无关 |
| $O(\log n)$ | 对数阶 | 二分查找 |
| $O(n)$ | 线性阶 | 线性查找 |
| $O(n \log n)$ | 线性对数阶 | 快速排序、归并排序平均情况 |
| $O(n^2)$ | 平方阶 | 冒泡排序、直接插入排序 |
| $O(n^3)$ | 立方阶 | 矩阵乘法 |
| $O(2^n)$ | 指数阶 | 汉诺塔问题 |
| $O(n!)$ | 阶乘阶 | 旅行商问题 |
复杂度从小到大排序：
$$O(1) < O(\log n) < O(n) < O(n \log n) < O(n^2) < O(n^3) < O(2^n) < O(n!)$$
2.4 递归的时间复杂度
递归主方法（Master Theorem）
对于形如以下的递归式：
$$T(n) = aT(n/b) + f(n)$$
其中，$a \geq 1$ 和 $b > 1$ 是常数，$f(n)$ 是一个渐进的正函数。
每次递归的时间复杂度不变的情况：
$$\text{总时间复杂度} = \text{递归的次数} \times \text{每次递归的时间复杂度}$$
3. 查找算法
3.1 顺序查找
从表的一端开始，逐个将记录的关键字和给定值进行比较。
- 时间复杂度：$O(n)$
- 空间复杂度：$O(1)$
3.2 折半查找（二分查找）
要求查找表必须是有序的。每次将待查记录所在区间缩小一半。
- 时间复杂度：$O(\log n)$
- 空间复杂度：$O(1)$
3.3 分块查找
将查找表分成若干块，块内无序，块间有序。先确定待查记录所在的块，再在块内顺序查找。
3.4 哈希表查找
哈希函数的构造方法
- 除留余数法：$H(key) = key \mod p$，其中 $p$ 为不大于表长的最大素数
处理冲突的方法
| 方法 | 说明 |
|---|---|
| 开放地址法 | 当冲突发生时，使用某种探测技术在哈希表中形成一个探测序列，沿此序列逐个单元查找 |
| 链地址法 | 将所有关键字为同义词的记录存储在一个单链表中 |
4. 排序算法
4.1 排序的基本概念
稳定性：若记录序列中有两个记录 $R_i$ 和 $R_j$，其关键字相同，即 $K_i = K_j$，且在排序前 $R_i$ 领先于 $R_j$，若排序后 $R_i$ 仍领先于 $R_j$，则称该排序方法是稳定的，否则是不稳定的。
4.2 简单排序
直接插入排序
将待排序的记录按其关键字大小插入到前面已经排好序的子表中的适当位置。
- 时间复杂度：$O(n^2)$
- 空间复杂度：$O(1)$
- 稳定性：稳定
简单选择排序
每一趟从待排序的记录中选出关键字最小的记录，顺序放在已排好序的子表的最后。
- 时间复杂度：$O(n^2)$
- 空间复杂度：$O(1)$
- 稳定性：不稳定
冒泡排序
两两比较相邻记录的关键字，如果反序则交换，直到没有反序的记录为止。
- 时间复杂度：$O(n^2)$
- 空间复杂度：$O(1)$
- 稳定性：稳定
4.3 高级排序
希尔排序（Shell Sort）
先将整个待排记录序列分割成若干子序列分别进行直接插入排序，待整个序列中的记录"基本有序"时，再对全体记录进行一次直接插入排序。
- 时间复杂度：约 $O(n^{1.3})$
- 空间复杂度：$O(1)$
- 稳定性：不稳定
快速排序（Quick Sort）
通过一趟排序将待排记录分割成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，然后分别对这两部分继续进行排序。
- 时间复杂度：平均 $O(n \log n)$，最坏 $O(n^2)$
- 空间复杂度：$O(\log n)$
- 稳定性：不稳定
堆排序（Heap Sort）
利用堆这种数据结构设计的排序算法。堆是一个近似完全二叉树的结构，并同时满足堆积性质。
- 时间复杂度：$O(n \log n)$
- 空间复杂度：$O(1)$
- 稳定性：不稳定
归并排序（Merge Sort）
采用分治法，将已有序的子序列合并，得到完全有序的序列。
- 时间复杂度：$O(n \log n)$
- 空间复杂度：$O(n)$
- 稳定性：稳定
4.4 排序算法总结
| 排序方法 | 平均时间 | 最坏时间 | 空间复杂度 | 稳定性 |
|---|---|---|---|---|
| 直接插入排序 | $O(n^2)$ | $O(n^2)$ | $O(1)$ | 稳定 |
| 简单选择排序 | $O(n^2)$ | $O(n^2)$ | $O(1)$ | 不稳定 |
| 冒泡排序 | $O(n^2)$ | $O(n^2)$ | $O(1)$ | 稳定 |
| 希尔排序 | $O(n^{1.3})$ | - | $O(1)$ | 不稳定 |
| 快速排序 | $O(n \log n)$ | $O(n^2)$ | $O(\log n)$ | 不稳定 |
| 堆排序 | $O(n \log n)$ | $O(n \log n)$ | $O(1)$ | 不稳定 |
| 归并排序 | $O(n \log n)$ | $O(n \log n)$ | $O(n)$ | 稳定 |
评论