数据结构比较
顺序表&链表
| 顺序表 | 链表 | |
|---|---|---|
| 空间 | O(1) | |
| 存取 | O(1) | O(n) |
| 插入删除 | O(n) | O(1) |
栈与递归
空间：O(n)，与递归树的深度成正比
时间：O(2^n)，与递归树的结点成正比
执行次数：
$$
f(n)=2^0+2^1+…+2^{n-2}+2^{n-1}f(1)=2^n-1
$$
串匹配
| BF | KMP | |
|---|---|---|
| 比较次数 | (n-m)*m+m | n |
| 时间 | O(n*m) | O(n+m),O(m)是求next的时间复杂度 |
二叉树
先中后序遍历
时间：O(n)，每个结点只访问一次
空间：O(n)，栈占用的最大辅助空间
图
存储
| item | 邻接矩阵 | 邻接表 |
|---|---|---|
| 空间 | $O(n^2)$ | 无向：$O(n+2e)$ 有向：$O(n+e)$ |
| 优点 | 容易求某顶点的度、判断顶点之间是否有边、找顶点的邻接点 | 空间效率高，容易找顶点的邻接点 |
| 缺点 | 对稀疏图，浪费空间 | 判断两顶点间是否有边需要搜索对应的单链表 |
| 适用 | 稠密图 | 稀疏图 |
遍历
| item | DFS | BFS |
|---|---|---|
| 时间 | 邻接矩阵：$O(n^2)$ 邻接表：$O(n+e)$ |
同DFS，时间复杂度只与存储结构有关，而与搜索路径无关 |
| 空间 | $O(n)$，借用堆栈 | $O(n)$，借用队列 |
最短路径
| item | Dijkstra | Floyd |
|---|---|---|
| 时间 | $O(n^2)$ |
查找
查找算法
| item | 顺序查找 | 折半查找 | 分块查找 | 二叉排序树 |
|---|---|---|---|---|
| 空间 | O(1) | |||
| 比较次数 | 总： success:$1+2+…+n=\frac{n*(n+1)}{2}$ fail: n*(n+1) |
单次： success: $<=d=\lfloor{log_2n}\rfloor-1$ fail: d or d-1 |
第i层的结点需要比较i次 | |
| ASL/时间 | 查找概率相等时 ASLs=(n+1)/2 ASLf=n+1 |
$O(log_2n)$ |
$ASL=L_b+L_w$ $log_2n<=ASL_{bs}<=\frac{n+1}{2}$ $ASL_bs≈log_2(\frac{n}{s}+1)+\frac{s}{2}$ s表示每块中的记录个数 |
$ASL=\frac{1}{n}\prod{im_i}$ 最好$log_2n$ 最坏(n+1)/2 |
| 优点 | 算法简单，对表结构(顺序or链式)无要求 | 插入和删除较容易，无需进行大量移动，适用于既要快速查找又经常动态变化 | ||
| 缺点 | n很大时查找效率低 | 必须是顺序存储的关键字有序的线性表 | 要增加一个索引表的存储空间并对初始索引表进行排序运算。 |
哈希冲突
| item | 线性探测 | 链地址 |
|---|---|---|
| 优点 | 只要哈希表未被填满，总能找到一个空地址解决冲突 | 非同义词不会冲突；动态申请适于表长不确定的情况 |
| 缺点 | 聚集现象 |
排序
插入排序
| item | 直接插入 | 折半插入 | 希尔排序 |
|---|---|---|---|
| 单次 | 最好：比较1次，不移动 最坏：第i趟比较i次，移动i+1次 |
插入第i个对象时比较$\lfloor log_2i\rfloor+1$ | |
| 比较次数 | 最好：n-1 最坏：$\sum_{i=2}^{n}{i}=\frac{(n+2)*(n-1)}{2}$ 平均：$\frac{n^2}{4}$ |
||
| 移动次数 | 最好：0 最坏：$\sum_{i=2}^{n}{i+1}=\frac{(n+4)*(n-1)}{2}$ 平均：$\frac{n^2}{4}$ |
||
| 时间 | $O(n^2)$ | ||
| 空间 | O(1) | ||
| 稳定 | 是 | 是 | 否 |
| 特点 | 比较次数和移动次数与初始排列有关 | 比较次数与待排序对象序列的初始排列无关，移动次数仍依赖。=>减少了比较次数但没有减少移动次数 |
交换排序
| item | 冒泡排序 | 快速排序 |
|---|---|---|
| 比较次数 | 最好：1趟排序，比较n-1次，不移动 最坏：需 n-1趟排序，第i趟比较n-i次，移动3(n-i)次=>n^2 |
最好：$nlog_2n$ 最坏：第i趟比较n-i次=>n^2 |
| 时间 | $O(n^2)$ | $O(nlog_2n)$ |
| 空间 | O(1) | $O(log_2n)$ |
| 稳定性 | 是 | 否 |
| 优点 | 每趟结束时，不仅能挤出一个最大值到最后面位置，还能同时部分理顺其他元素； 一旦下趟没有交换，还可提前结束排序 |
|
| 特点 | 比较次数和移动次数与初始排列有关 | 平均计算时间是最好的 |
选择排序
| item | 简单选择 | 堆排序 | 归并排序 | 基数排序 |
|---|---|---|---|---|
| 比较次数 | $\sum_{i=1}^{n-1}=\frac{1}{2}(n^2-n)==>n^2$ | |||
| 移动次数 | 最好：0 最坏：3n-1==>n |
|||
| 时间 | $O(n^2)$ | $O(nlog_2n)$ | $O(nlog_2n)$ | $O(d(n+rd))$ |
| 空间 | O(1) | O(1) | O(n) | O(n+rd)，rd表示关键字的取值范围 |
| 稳定性 | 是 | 否 | 是 | 是 |