公式速查

教材导航

算法与线性结构

树与图

关系公式与条件入口
树的边数e=n−1e=n-1,非空树5.1.3 树的性质
二叉树度数n0=n2+1n_0=n_2+1,非空二叉树5.2.1.2 二叉树的性质
二叉树每层最多结点第 ii 层 2i−12^{i-1},根为第 1 层5.2.1.2 二叉树的性质
高度 hh 的二叉树最多结点2h−12^h-15.2.1.2 二叉树的性质
完全二叉树高度⌊log⁡2n⌋+1\lfloor\log_2 n\rfloor+1,n>0n>05.2.1.1 几种特殊的二叉树
带权路径长度WPL=∑wiliWPL=\sum w_i l_i,根深度为 05.5.1 哈夫曼树和哈夫曼编码
哈夫曼树实际结点nn 个叶,共 2n−12n-1 个结点5.5.1.1 哈夫曼树的构造
无向图度数和∑d(v)=2m\sum d(v)=2m6.1.1 图的定义与基本术语
有向图出入度和∑d+(v)=∑d−(v)=m\sum d^+(v)=\sum d^-(v)=m6.1.1 图的定义与基本术语
简单图最多边数无向 n(n−1)/2n(n-1)/2;有向 n(n−1)n(n-1)6.1.1 图的定义与基本术语
无向生成森林cc 个分量时 n−cn-c 条边6.3.3 图的遍历与图的连通性
BFS、DFS 时间邻接表 O(n+m)O(n+m);矩阵 O(n2)O(n^2)6.3 图的遍历

6.4.2.1 Dijkstra 算法:dist[v]←min⁡(dist[v],dist[u]+w(u,v))dist[v]\leftarrow\min(dist[v],dist[u]+w(u,v)),要求非负边。

6.4.2.2 Floyd 算法:D[i][j]←min⁡(D[i][j],D[i][k]+D[k][j])D[i][j]\leftarrow\min(D[i][j],D[i][k]+D[k][j]),kk 在最外层。

6.4.5 关键路径:

ve[v]=max⁡u→v{ve[u]+w(u,v)},vl[u]=min⁡u→v{vl[v]−w(u,v)}ve[v]=\max_{u\to v}\{ve[u]+w(u,v)\},\quad vl[u]=\min_{u\to v}\{vl[v]-w(u,v)\} e(u,v)=ve[u],l(u,v)=vl[v]−w(u,v),余量=l−ee(u,v)=ve[u],\quad l(u,v)=vl[v]-w(u,v),\quad \text{余量}=l-e

查找

  • 7.1 查找的基本概念:ASL=∑piCiASL=\sum p_iC_i,成功、失败分别建立概率空间。
  • 7.2.1 一般线性表的顺序查找:等概率成功 ASL=(n+1)/2ASL=(n+1)/2;失败是否计哨兵按题意。
  • 7.2.2 折半查找:n>0n>0 时最坏记录比较 ⌊log⁡2n⌋+1=⌈log⁡2(n+1)⌉\lfloor\log_2n\rfloor+1=\lceil\log_2(n+1)\rceil。
  • 7.2.3 分块查找:索引和块内都顺序查且 n=bsn=bs 时,ASL=(b+1)/2+(s+1)/2ASL=(b+1)/2+(s+1)/2,s≈ns\approx\sqrt n 较小。
  • 7.3.2.3 AVL 的查找与高度界:Nh=Nh−1+Nh−2+1N_h=N_{h-1}+N_{h-2}+1,N0=0,N1=1N_0=0,N_1=1。
  • 7.3.3 红黑树:红黑树高度 h≤2log⁡2(n+1)h\le2\log_2(n+1),nn 为实际记录结点数。
  • 7.4.1.2 B 树的高度:mm 阶 B 树,t=⌈m/2⌉t=\lceil m/2\rceil,2th−1−1≤n≤mh−12t^{h-1}-1\le n\le m^h-1,hh 不含外部空结点层。
  • 7.5.4 散列查找及性能分析:装填因子 α=n/m\alpha=n/m;失败 ASL 的分母由可能初始散列地址及概率决定。

排序与外存

  • 8.3.1 冒泡排序:相邻逆序交换总次数等于初始逆序对数。
  • 8.4.1 简单选择排序:简单选择关键字比较固定为 n(n−1)/2n(n-1)/2 次。
  • 8.4.2.1 建堆与堆排序:自底向上建堆 O(n)O(n);整体排序最坏 O(nlog⁡n)O(n\log n)。
  • 8.5.1 归并排序:两有序段长 a,b>0a,b>0,最多比较 a+b−1a+b-1 次;二路归并共 ⌈log⁡2n⌉\lceil\log_2n\rceil 趟。
  • 8.5.2 基数排序:dd 位、基数 rr,时间 O(d(n+r))O(d(n+r))。
  • 8.5.3 计数排序:值域 kk 的频次计数排序 O(n+k)O(n+k);两两比较计名次为 O(n2)O(n^2)。
  • 8.7.2 外部排序的方法:rr 个段、kk 路平衡归并,s=⌈log⁡kr⌉s=\lceil\log_k r\rceil;NN 块全量读写的简化总 I/O 为 2N(1+s)2N(1+s)。
  • 8.7.5 最佳归并树:补虚段 z=((k−1)−((r−1) mod (k−1))) mod (k−1)z=((k-1)-((r-1)\bmod(k-1)))\bmod(k-1);最佳归并记录读写量为 2WPL2WPL,块 I/O 需另算。

复杂度和稳定性总表见 8.6.1 内部排序算法的比较。