公式速查
算法与线性结构
- 1.2 算法和算法评价:顺序执行相加,嵌套按实际迭代次数求和;最坏、平均和均摊是不同指标。
- 3.2.2.1 循环队列:牺牲一个位置的循环队列,空为
front==rear,满为(rear+1)%MaxSize==front,长度(rear-front+MaxSize)%MaxSize。 - 3.4.2 数组的存储结构:0 起始二维数组 ,元素宽 ,行优先偏移 ,列优先偏移 。
- 4.2.1 简单的模式匹配算法:朴素匹配最坏 ;4.2.2 串的模式匹配算法——KMP算法 预处理和匹配合计 。
next的下标规则必须保持一致。
树与图
| 关系 | 公式与条件 | 入口 |
|---|---|---|
| 树的边数 | ,非空树 | 5.1.3 树的性质 |
| 二叉树度数 | ,非空二叉树 | 5.2.1.2 二叉树的性质 |
| 二叉树每层最多结点 | 第 层 ,根为第 1 层 | 5.2.1.2 二叉树的性质 |
| 高度 的二叉树最多结点 | 5.2.1.2 二叉树的性质 | |
| 完全二叉树高度 | , | 5.2.1.1 几种特殊的二叉树 |
| 带权路径长度 | ,根深度为 0 | 5.5.1 哈夫曼树和哈夫曼编码 |
| 哈夫曼树实际结点 | 个叶,共 个结点 | 5.5.1.1 哈夫曼树的构造 |
| 无向图度数和 | 6.1.1 图的定义与基本术语 | |
| 有向图出入度和 | 6.1.1 图的定义与基本术语 | |
| 简单图最多边数 | 无向 ;有向 | 6.1.1 图的定义与基本术语 |
| 无向生成森林 | 个分量时 条边 | 6.3.3 图的遍历与图的连通性 |
| BFS、DFS 时间 | 邻接表 ;矩阵 | 6.3 图的遍历 |
6.4.2.1 Dijkstra 算法:,要求非负边。
6.4.2.2 Floyd 算法:, 在最外层。
查找
- 7.1 查找的基本概念:,成功、失败分别建立概率空间。
- 7.2.1 一般线性表的顺序查找:等概率成功 ;失败是否计哨兵按题意。
- 7.2.2 折半查找: 时最坏记录比较 。
- 7.2.3 分块查找:索引和块内都顺序查且 时,, 较小。
- 7.3.2.3 AVL 的查找与高度界:,。
- 7.3.3 红黑树:红黑树高度 , 为实际记录结点数。
- 7.4.1.2 B 树的高度: 阶 B 树,,, 不含外部空结点层。
- 7.5.4 散列查找及性能分析:装填因子 ;失败 ASL 的分母由可能初始散列地址及概率决定。
排序与外存
- 8.3.1 冒泡排序:相邻逆序交换总次数等于初始逆序对数。
- 8.4.1 简单选择排序:简单选择关键字比较固定为 次。
- 8.4.2.1 建堆与堆排序:自底向上建堆 ;整体排序最坏 。
- 8.5.1 归并排序:两有序段长 ,最多比较 次;二路归并共 趟。
- 8.5.2 基数排序: 位、基数 ,时间 。
- 8.5.3 计数排序:值域 的频次计数排序 ;两两比较计名次为 。
- 8.7.2 外部排序的方法: 个段、 路平衡归并,; 块全量读写的简化总 I/O 为 。
- 8.7.5 最佳归并树:补虚段 ;最佳归并记录读写量为 ,块 I/O 需另算。
复杂度和稳定性总表见 8.6.1 内部排序算法的比较。