计算机网络与数据结构考研核心公式笔记

计算机网络考研核心公式笔记 (完整汇总版)

第一章：概述与基础

1. 速率 (Rate)

   • 单位换算：

     $$1 \text{ kbps} = 10^3 \text{ bps} \quad (k = 10^3)$$ $$1 \text{ Mbps} = 10^6 \text{ bps} \quad (M = 10^6)$$ $$1 \text{ Gbps} = 10^9 \text{ bps} \quad (G = 10^9)$$

2. 时延 (Delay)

   • 总时延 (Total Delay):

     $$D_{总} = D_{发送} + D_{传播} + D_{处理} + D_{排队}$$

   • 发送时延 (Transmission Delay)：也称传输时延，是将数据从主机/路由器推向链路所需的时间。

     $$D_{发送} = \frac{\text{数据块长度 (bit)}}{\text{信道带宽 (bit/s)}}$$

   • 传播时延 (Propagation Delay)：电磁波在信道中传播一定距离所需的时间。

     $$D_{传播} = \frac{\text{信道长度 (m)}}{\text{电磁波在信道上的传播速率 (m/s)}}$$

     注：在真空/空气中传播速率约为 $3.0 \times 10^8$ m/s，在铜线或光纤中约为 $2.0 \sim 2.3 \times 10^8$ m/s。

3. 往返时间 (RTT - Round-Trip Time)

   • 从发送方发送数据开始，到发送方收到接收方确认的总时间。RTT 在很大程度上取决于传播时延。

     $$RTT \approx 2 \times D_{传播} \quad (\text{在忽略处理、排队和确认帧发送时延的理想情况下})$$

4. 时延带宽积 (Delay-Bandwidth Product)

   • 表示“链路的容量”，即某时刻已发出但尚未到达对端的数据量，也称为“以比特为单位的链路长度”。

     $$\text{时延带宽积} = D_{传播} \times \text{信道带宽}$$

5. 信道利用率 (Channel Utilization)

   • 有数据通过的时间占总时间的比例。在停止-等待协议的简化模型下：

     $$U = \frac{D_{发送}}{D_{发送} + RTT}$$

第二章：物理层

1. 奈奎斯特定理 (Nyquist’s Theorem) - 无噪声

   • 描述了理想无噪声信道的极限数据传输速率。

   • $W$ 是信道带宽 (Hz)，$V$ 是码元离散电平的数目。

     $$C_{max} = 2W \log_2 V \quad (\text{bit/s})$$

2. 香农定理 (Shannon’s Theorem) - 有噪声

   • 描述了有高斯白噪声信道的极限数据传输速率，是理论上限。

   • $W$ 是信道带宽 (Hz)，$S/N$ 是信噪比（注意 $S/N$ 是一个比值，无单位）。

     $$C_{max} = W \log_2(1 + \frac{S}{N}) \quad (\text{bit/s})$$

3. 分贝与信噪比的关系

   • 工程上常用分贝 (dB) 度量信噪比：

     $$\text{信噪比 (dB)} = 10 \log_{10}(\frac{S}{N})$$

   • 从分贝反推 $S/N$ 以代入香农公式：

     $$\frac{S}{N} = 10^{\frac{\text{信噪比 (dB)}}{10}}$$

第三章：数据链路层

1. 最短帧长 (CSMA/CD)

   • 为了确保在发送完成前能检测到碰撞，必须满足：

     $$\text{帧的发送时延} \ge 2 \times \text{端到端传播时延 (RTT)}$$ $$\frac{\text{最短帧长 (bit)}}{\text{数据率 (bps)}} \ge \text{争用期}$$

   • 在 10 Mbps 以太网中，争用期为 51.2μs，因此最短帧长为 $512 bit$，即 $64$ 字节。

2. 停止-等待协议 (Stop-and-Wait)

   • 信道利用率 (U)：$a$ 为传播时延与发送时延之比。

     $$U = \frac{T_{发送}}{T_{发送} + RTT + T_{确认}}$$

     简化模型（忽略确认帧发送时间）:

     $$U = \frac{T_{发送}}{T_{发送} + RTT} = \frac{1}{1 + \frac{RTT}{T_{发送}}} = \frac{1}{1 + 2a} \quad (\text{其中 } a = \frac{T_{传播}}{T_{发送}})$$

3. 后退 N 帧协议 (Go-Back-N, GBN)

   • 发送窗口 $W_T$：$n$ 为帧序号的比特数。

     $$1 \le W_T \le 2^n - 1$$

   • 接收窗口 $W_R$：

     $$W_R = 1$$

   • 信道利用率 (U) (无差错时):

     $$U = \begin{cases} \frac{W_T}{1+2a} & W_T < 1+2a \\ 1 & W_T \ge 1+2a \end{cases}$$

4. 选择重传协议 (Selective Repeat, SR)

   • 发送窗口 $W_T$ 和接收窗口 $W_R$：

     $$W_T + W_R \le 2^n$$

     通常取:

     $$W_T = W_R = 2^{n-1}$$

5. 海明距离与检错/纠错能力

   • 检错能力：检测 $k$ 个位的错误，要求最小海明距离 $d_min$ 满足：

     $$d_{min} \ge k + 1$$

   • 纠错能力：纠正 $t$ 个位的错误，要求最小海明距离 $d_min$ 满足：

     $$d_{min} \ge 2t + 1$$

第四章：网络层

1. IP 地址与子网划分

   • 网络地址：

     $$\text{网络地址} = \text{IP 地址} \quad \text{AND} \quad \text{子网掩码}$$

   • 可分配的主机数：$N$ 为主机号的比特数。

     $$\text{可分配的主机数} = 2^N - 2$$

     减 2 是因为主机号全 0（网络地址）和全 1（广播地址）不可分配。

   • CIDR (无类域间路由)：
     IP 地址表示为 $a.b.c.d/x$，其中 $x$ 是网络前缀的长度。

     $$\text{地址块中的地址总数} = 2^{32 - x}$$ $$\text{子网掩码的点分十进制} \leftarrow \text{连续 } x \text{ 个1和 } 32-x \text{ 个0}$$

2. MTU 与 IP 分片

   • 最大数据长度：IP 数据报中数据部分的最大长度。

     $$\text{最大数据长度} = \text{MTU} - \text{IP 头部长度}$$

   • 片偏移 (Fragment Offset)：以 8 字节为单位。

     $$\text{片偏移字段值} = \frac{\text{该分片数据部分首字节在原数据报中的偏移量}}{8}$$

第五章：传输层 (TCP)

1. 最大报文段长度 (MSS - Maximum Segment Size)

   • TCP 数据部分的最大长度。

     $$MSS = \text{MTU} - \text{IP 头部长度} - \text{TCP 头部长度}$$

2. 加权平均往返时间 $RTT_S$ (Smoothed RTT)

   • $α$ 是平滑因子，通常为 0.125。

     $$\text{新的 } RTT_S = (1 - \alpha) \times (\text{旧的 } RTT_S) + \alpha \times (\text{新的 RTT 样本})$$

3. 超时重传时间 (RTO - Retransmission Timeout)

   • $RTT_D$ 是 RTT 的偏差的加权平均值。

     $$RTO = RTT_S + 4 \times RTT_D$$

4. TCP 流量控制

   • 发送方有效窗口：发送方还能发送的数据量。

     $$\text{有效窗口} = \text{min}(\text{拥塞窗口 } cwnd, \text{接收方通告窗口 } rwnd)$$

5. TCP 拥塞控制

   • 慢开始 (Slow Start)：$cwnd < ssthresh$ 时，每经过一个 RTT，$cwnd$ 翻倍。

     $$cwnd_{n+1} = 2 \times cwnd_n \quad (\text{每经过一个 RTT})$$

     更精确地：每收到一个 ACK，$cwnd$ 增加 1 个 MSS。

   • 拥塞避免 (Congestion Avoidance)：$cwnd \ge ssthresh$ 时，$cwnd$ 线性增长。

     $$cwnd_{n+1} = cwnd_n + 1 \text{ MSS} \quad (\text{每经过一个 RTT})$$

   • 拥塞发生时 (超时)：

     $$ssthresh = \max(\frac{cwnd}{2}, 2 \times MSS)$$ $$cwnd = 1 \times MSS$$

   • 拥塞发生时 (快重传/快恢复 - 收到 3 个重复 ACK)：

     $$ssthresh = \max(\frac{cwnd}{2}, 2 \times MSS)$$ $$cwnd = ssthresh$$

     然后进入拥塞避免阶段。

数据结构考研核心公式与知识点笔记

第一章：绪论 (算法复杂度分析)

1. 时间复杂度 (Time Complexity)

   • 定义: $T(n) = O(f(n))$ 表示存在常数 $C$ 和 $n₀$，使得当 $n ≥ n₀$ 时，有 $T(n) ≤ C * f(n)$。

   • 常见复杂度排序:

     $$O(1) < O(\log_2 n) < O(n) < O(n \log_2 n) < O(n^2) < O(n^3) < O(2^n) < O(n!) < O(n^n)$$

2. 空间复杂度 (Space Complexity)

   • 定义: $S(n) = O(g(n))$ 表示算法所需的辅助空间与 $g(n)$ 成正比。
   • 原地工作 (In-place): 算法所需的辅助空间是常数，即 $O(1)$。

第二章：线性表 (Linear List)

1. 顺序表 (Sequential List)

   • 查找/访问: $O(1)$

   • 插入/删除 (平均): $O(n)$

     • 插入操作平均需要移动 $n/2$ 个元素。
     • 删除操作平均需要移动 $(n-1)/2$ 个元素。

2. 链表 (Linked List)

   • 查找/访问: $O(n)$
   • 插入/删除 (给定指针): $O(1)$

第三章：栈和队列 (Stack & Queue)

1. 栈 (Stack)

   • 特性: 后进先出 (LIFO - Last In First Out)。

   • n个不同元素入栈，出栈序列种类数 (卡特兰数 Catalan Number):

     $$\text{种类数} = \frac{1}{n+1} C_{2n}^{n} = \frac{(2n)!}{(n+1)!n!}$$

2. 队列 (Queue)

   • 特性: 先进先出 (FIFO - First In First Out)。

   • 循环队列 (用数组实现): 设数组大小为 $MaxSize$。

     • 队空条件:

       $$front == rear$$

     • 队满条件 (牺牲一个空间):

       $$(rear + 1) \pmod{MaxSize} == front$$

     • 队列长度 (牺牲一个空间):

       $$\text{Length} = (rear - front + MaxSize) \pmod{MaxSize}$$

     • 入队操作:

       $$rear = (rear + 1) \pmod{MaxSize}$$

     • 出队操作:

       $$front = (front + 1) \pmod{MaxSize}$$

第四章：串 (String)

1. KMP 算法

   • next 数组计算: $next[j]$ 表示 $p[0…j-1]$ 中最长相等前后缀的长度。

     • $next[0] = -1$ (或 $next[1] = 0$，取决于数组下标从0还是1开始)。
   • 时间复杂度: $O(m+n)$，其中 $m$ 是模式串长度，$n$ 是主串长度。

第五章：数组和广义表

1. 二维数组的地址计算

   • 设数组 $A[m][n]$，每个元素占 $L$ 个存储单元，起始地址为 $LOC(A[0][0])$。

   • 按行优先存储: $A[i][j]$ 的地址

     $$LOC(A[i][j]) = LOC(A[0][0]) + (i \times n + j) \times L$$

   • 按列优先存储: $A[i][j]$ 的地址

     $$LOC(A[i][j]) = LOC(A[0][0]) + (j \times m + i) \times L$$

2. 对称矩阵的压缩存储

   • 存储 $n(n+1)/2$ 个元素。对于下三角部分的元素 $A[i][j]$ (其中 $i ≥ j$)，其在一维数组 $B$ 中的下标 $k$ 为：

     $$k = \frac{i(i+1)}{2} + j \quad (\text{当 i, j 从 0 开始计数})$$

第六章：树与二叉树 (Tree & Binary Tree)

1. 二叉树的性质

   • 性质1: 在二叉树的第 $i$ 层上至多有 $2^{i-1}$ 个结点 ($i ≥ 1$)。

   • 性质2: 深度为 $k$ 的二叉树至多有 $2^k - 1$ 个结点 ($k ≥ 1$)。

   • 性质3 (结点关系): 对任何一棵二叉树，若 $n₀$ 是叶子结点数，$n₂$ 是度为2的结点数，则：

     $$n_0 = n_2 + 1$$

   • 结点总数:

     $$n = n_0 + n_1 + n_2$$

2. 满二叉树 (Full Binary Tree)

   • 深度为 $k$ 且含有 $2^k - 1$ 个结点的二叉树。

3. 完全二叉树 (Complete Binary Tree)

   • 性质:

     • 具有 $n$ 个结点的完全二叉树，深度 $k$ 为：

       $$k = \lfloor \log_2 n \rfloor + 1$$

     • 对于结点 $i$ (从1开始编号):

       • 若 $i=1$，则为根节点；若 $i>1$，其父节点为 $\lfloor i/2 \rfloor$。
       • 若 $2i > n$，则结点 $i$ 无左孩子。否则，其左孩子是 $2i$。
       • 若 $2i+1 > n$，则结点 $i$ 无右孩子。否则，其右孩子是 $2i+1$。

4. 哈夫曼树 (Huffman Tree)

   • 带权路径长度 (WPL):

     $$WPL = \sum_{i=1}^{n} w_i l_i$$

     其中 $w_i$ 是叶子结点的权值，$l_i$ 是该叶子结点到根的路径长度。

   • 哈夫曼树的结点总数: 对于 $n$ 个叶子结点，构造出的哈夫曼树共有 $2n-1$ 个结点。

第七章：图 (Graph)

1. 图的存储

   • 邻接矩阵: $n$ 个顶点的图，矩阵大小为 $n x n$。

     • 无向图的度: $TD(vi) = \sum{j=0}^{n-1} A[i][j]$
     • 有向图的出度: $OD(vi) = \sum{j=0}^{n-1} A[i][j]$
     • 有向图的入度: $ID(vi) = \sum{j=0}^{n-1} A[j][i]$

   • 邻接表:

     • 无向图的边数 $e$: $e = (\sum \text{所有顶点度数}) / 2$
     • 有向图的边数 $e$: $e = \sum \text{所有顶点的出度} = \sum \text{所有顶点的入度}$

2. 图的遍历

   • DFS (深度优先): 类似树的先序遍历，用栈实现。
   • BFS (广度优先): 类似树的层次遍历，用队列实现。

3. 最小生成树 (MST)

   • 对于有 $n$ 个顶点的连通图，其MST有且仅有 $n-1$ 条边。
   • Prim 算法: 时间复杂度 $O(|V|^2)$ (邻接矩阵) 或 $O(|E|\log|V|)$ (邻接表+优先队列)。
   • Kruskal 算法: 时间复杂度 $O(|E|\log|E|)$ (主要取决于对边排序的时间)。

4. 最短路径 (Shortest Path)

   • Dijkstra 算法: 单源最短路径，不能处理带负权边的图。时间复杂度 $O(|V|^2)$ (邻接矩阵) 或 $O(|E|\log|V|)$ (邻接表+优先队列)。
   • Floyd 算法: 所有顶点对之间的最短路径，可以处理带负权边的图，但不能处理带负权回路的图。时间复杂度 $O(|V|^3)$。

第八章：查找 (Searching)

1. 顺序查找

   • 平均查找长度 (ASL): $(n+1)/2$

2. 折半查找 (二分查找)

   • 前提: 表必须有序。

   • 判定树:

     • 查找成功时的ASL: $O(\log_2 n)$
     • 查找失败时的ASL: $O(\log_2 n)$
   • 时间复杂度: $O(\log_2 n)$

3. 散列表 (哈希表)

   • 散列函数构造: 直接定址法、除留余数法、数字分析法等。

   • 冲突处理: 开放定址法 (线性探测、平方探测)、链地址法 (拉链法)。

   • 装填因子 α:

     $$\alpha = \frac{\text{表中记录数 } n}{\text{散列表长度 } m}$$

   • 平均查找长度 (ASL): 主要受装填因子 $α$ 影响。

     • 链地址法 (成功): $ASL \approx 1 + \alpha/2$
     • 线性探测法 (失败): $ASL \approx 1/(1-\alpha)$

第九章：排序 (Sorting)

1. 各种排序算法的性能

   • 时间复杂度:

     • $O(n^2)$: 冒泡、简单选择、直接插入
     • $O(n \log_2 n)$: 希尔 (不稳定)、堆排序、快速排序 (不稳定)、归并排序
     • $O(n)$: 基数排序

   • 空间复杂度:

     • $O(1)$: 冒泡、选择、插入、希尔、堆排序
     • $O(\log_2 n)$ ~ $O(n)$: 快速排序 (递归深度)
     • $O(n)$: 归并排序
     • $O(r)$ (r为关键字基数): 基数排序

   • 稳定性:

     • 稳定: 冒泡、插入、归并、基数
     • 不稳定: 选择、希尔、快速、堆