公式索引

变量

$y$

在“程序与状态转换”中作为等号左侧的目标量参与关系计算，单位：不适用

$f$

在“程序与状态转换”中作为等号右侧的输入量或系数参与关系计算，单位：不适用

$x$

在“程序与状态转换”中作为等号右侧的输入量或系数参与关系计算，单位：不适用

相关概念

适用与边界

• 应用：把条件分支、循环控制流不变量与终止条件整理为可检查的关系、判据或算法步骤；涉及定量模型时写出公式，并说明符号、适用条件，以及需要时的单位或复杂度。
• 边界：编写小程序前，我们至少需要说明：接受什么输入、类型与单位；对非法或边界输入做什么；成功返回什么类型和值；是否修改外部状态；是否保证终止。
• 推导：C00 · 程序、类型、控制流与函数

变量

$N$

在“地址前缀与子网范围”中作为等号左侧的目标量参与关系计算，单位：不适用

$p$

在“地址前缀与子网范围”中作为等号右侧的输入量或系数参与关系计算，单位：不适用

相关概念

适用与边界

• 应用：把路由聚合和最长前缀匹配整理为可检查的关系、判据或算法步骤；涉及定量模型时写出公式，并说明符号、适用条件，以及需要时的单位或复杂度。
• 边界：对常规带广播地址的子网，主机地址通常排除网络地址和广播地址，但点对点链路上的 等情形有专门规则；计算地址总数的公式始终适用，计算终端数量时则必须说明子网类型。
• 推导：C05 · IP 地址与路由

变量

$\tau$

在“对照与潜在结果”中作为等号左侧的目标量参与关系计算，单位：不适用

$Y$

在“对照与潜在结果”中作为等号右侧的输入量或系数参与关系计算，单位：不适用

相关概念

适用与边界

• 应用：把随机分配、分层阻断与盲法实施整理为可检查的关系、判据或算法步骤；涉及定量模型时写出公式，并说明符号、适用条件，以及需要时的单位或复杂度。
• 边界：用 $Y_i(1)$ 与 $Y_i(0)$ 表示单位 $i$ 的两个潜在结果，个体处理效应为 $Y_i(1)-Y_i(0)$，却无法同时观测。
• 推导：C02 · 对照、随机化与功效分析

变量

$N_{ij}$

用下标 ij 区分 N 的分量、样本或离散状态，单位：不适用

$M_{ij}$

用下标 ij 区分 M 的分量、样本或离散状态，单位：不适用

$C_{ij}$

用下标 ij 区分 C 的分量、样本或离散状态，单位：不适用

相关概念

适用与边界

• 应用：把多实例分配与安全序列的逐步检查整理为可检查的关系、判据或算法步骤；涉及定量模型时写出公式，并说明符号、适用条件，以及需要时的单位或复杂度。
• 边界：安全检查要在试分配后的完整状态上执行，不能只检查空闲资源是否够用。
• 推导：C04 · 死锁与资源分配

变量

$d$

在“发送时延与传播时延”中作为等号左侧的目标量参与关系计算，单位：不适用

$L$

在“发送时延与传播时延”中作为等号右侧的输入量或系数参与关系计算，单位：不适用

$R$

在“发送时延与传播时延”中作为等号右侧的输入量或系数参与关系计算，单位：不适用

相关概念

适用与边界

• 应用：把单跳时延与多跳存储转发整理为可检查的关系、判据或算法步骤；涉及定量模型时写出公式，并说明符号、适用条件，以及需要时的单位或复杂度。
• 边界：正文未把极限情形单列为独立公式；适用边界以本小节声明的定义域、假设和边界条件为限。
• 推导：C05 · 网络分层与时延

变量

$T$

在“分治的四个部件”中作为等号左侧的目标量参与关系计算，单位：不适用

$n$

在“分治的四个部件”中作为等号左侧的目标量参与关系计算，单位：不适用

$a$

在“分治的四个部件”中作为等号右侧的输入量或系数参与关系计算，单位：不适用

$b$

在“分治的四个部件”中作为等号右侧的输入量或系数参与关系计算，单位：不适用

$f$

在“分治的四个部件”中作为等号右侧的输入量或系数参与关系计算，单位：不适用

$\Theta$

在“分治的四个部件”中作为等号右侧的输入量或系数参与关系计算，单位：不适用

相关概念

适用与边界

• 应用：把快速排序的划分过程与最坏输入整理为可检查的关系、判据或算法步骤；涉及定量模型时写出公式，并说明符号、适用条件，以及需要时的单位或复杂度。
• 边界：递推子问题尺寸不等、子问题数随 $n$ 改变或 $f$ 剧烈振荡时，标准 Master 形式未必适用，应直接展开递归树、代入证明或使用更一般定理。
• 推导：C01 · 分治、贪心与排序

变量

$T$

在“建立时间与时钟周期”中作为等号右侧的输入量或系数参与关系计算，单位：不适用

$t_{cq}$

用下标 cq 区分 t 的分量、样本或离散状态，单位：不适用

$t_{logic}$

用下标 logic 区分 t 的分量、样本或离散状态，单位：不适用

$t_{setup}$

用下标 setup 区分 t 的分量、样本或离散状态，单位：不适用

相关概念

适用与边界

• 应用：把寄存器和有限状态机整理为可检查的关系、判据或算法步骤；涉及定量模型时写出公式，并说明符号、适用条件，以及需要时的单位或复杂度。
• 边界：保持时间约束检查最快路径，防止新数据过早到达接收端，不能只检查上式中的最长延迟。
• 推导：C03 · 数字逻辑与时序电路

变量

$G$

在“接收窗口与拥塞窗口”中作为等号右侧的输入量或系数参与关系计算，单位：不适用

$R$

在“接收窗口与拥塞窗口”中作为等号右侧的输入量或系数参与关系计算，单位：不适用

$W$

在“接收窗口与拥塞窗口”中作为等号右侧的输入量或系数参与关系计算，单位：不适用

相关概念

适用与边界

• 应用：把序号、累计确认与连接状态整理为可检查的关系、判据或算法步骤；涉及定量模型时写出公式，并说明符号、适用条件，以及需要时的单位或复杂度。
• 边界：这个式子没有描述连接启动、具体拥塞控制算法或重传开销；它适合检查窗口大小是否足以维持目标速率，不能直接预测任意网络中的下载速度。
• 推导：C05 · UDP 与 TCP

变量

$x$

在“课程平均分与人数”中作为等号左侧的目标量参与关系计算，单位：不适用

相关概念

适用与边界

• 应用：把分组聚合、空值与统计粒度整理为可检查的关系、判据或算法步骤；涉及定量模型时写出公式，并说明符号、适用条件，以及需要时的单位或复杂度。
• 边界：两者筛选阶段和统计总体不同，不能互换。
• 推导：C06 · SQL 查询与聚合

变量

$k$

在“例 1：反复在表头插入的成本”中作为等号左侧的目标量参与关系计算，单位：不适用

$n$

在“例 1：反复在表头插入的成本”中作为等号右侧的输入量或系数参与关系计算，单位：不适用

$\Theta$

在“例 1：反复在表头插入的成本”中作为等号右侧的输入量或系数参与关系计算，单位：不适用

相关概念

适用与边界

• 应用：把栈、队列与遍历顺序整理为可检查的关系、判据或算法步骤；涉及定量模型时写出公式，并说明符号、适用条件，以及需要时的单位或复杂度。
• 边界：两者对空结构操作都要定义失败，不能随意返回一个可能与合法元素冲突的特殊值。
• 推导：C01 · 序列、栈、队列、树与堆

变量

$N_{0}$

用下标 0 区分 N 的分量、样本或离散状态，单位：不适用

$N_{j+1}$

用下标 j+1 区分 N 的分量、样本或离散状态，单位：不适用

$N_{j}$

用下标 j 区分 N 的分量、样本或离散状态，单位：不适用

$N_{k}$

用下标 k 区分 N 的分量、样本或离散状态，单位：不适用

$k$

在“连续创建的进程数量”中作为等号右侧的输入量或系数参与关系计算，单位：不适用

相关概念

适用与边界

• 应用：把进程创建和文件描述符的继承关系整理为可检查的关系、判据或算法步骤；涉及定量模型时写出公式，并说明符号、适用条件，以及需要时的单位或复杂度。
• 边界：计数依赖控制流，不能只数源文件中出现几次调用名。
• 推导：C04 · 进程与系统调用

变量

相关概念

适用与边界

• 应用：把交换机学习、泛洪与广播域整理为可检查的关系、判据或算法步骤；涉及定量模型时写出公式，并说明符号、适用条件，以及需要时的单位或复杂度。
• 边界：全双工点对点链路分别承担两个方向的发送，课堂上讨论的共享介质碰撞机制只适用于相应的半双工模型。
• 推导：C05 · 以太网与交换

变量

$t_{avg}$

用下标 avg 区分 t 的分量、样本或离散状态，单位：不适用

$t_{h}$

用下标 h 区分 t 的分量、样本或离散状态，单位：不适用

$m$

在“平均访问时间与写入策略”中作为等号右侧的输入量或系数参与关系计算，单位：不适用

$p$

在“平均访问时间与写入策略”中作为等号右侧的输入量或系数参与关系计算，单位：不适用

相关概念

适用与边界

• 应用：把访问轨迹与映射冲突整理为可检查的关系、判据或算法步骤；涉及定量模型时写出公式，并说明符号、适用条件，以及需要时的单位或复杂度。
• 边界：描述写行为时应同时给出这两个维度，不能只说采用缓存写入就推断总线流量。
• 推导：C03 · 存储层次与缓存

变量

$P$

在“筛选、连接、聚合与派生变量”中作为等号左侧的目标量参与关系计算，单位：不适用

$E$

在“筛选、连接、聚合与派生变量”中作为等号右侧的输入量或系数参与关系计算，单位：不适用

$t$

在“筛选、连接、聚合与派生变量”中作为等号右侧的输入量或系数参与关系计算，单位：不适用

相关概念

适用与边界

• 应用：把数据血缘图、转换依赖与影响追踪整理为可检查的关系、判据或算法步骤；涉及定量模型时写出公式，并说明符号、适用条件，以及需要时的单位或复杂度。
• 边界：派生变量要给公式、输入列、单位和边界。
• 推导：C02 · 数据变换、血缘与版本

变量

$x$

在“舍入、消去与稳定改写”中作为等号右侧的输入量或系数参与关系计算，单位：不适用

相关概念

适用与边界

• 应用：把向量化归约、索引切片与临时分配整理为可检查的关系、判据或算法步骤；涉及定量模型时写出公式，并说明符号、适用条件，以及需要时的单位或复杂度。
• 边界：容差还应覆盖算法条件数和累计步数，不能固定一个对所有量纲通用的阈值。
• 推导：C00 · 数组、向量化与数值精度

变量

$\eta$

在“时间片轮转”中作为等号左侧的目标量参与关系计算，单位：不适用

$q$

在“时间片轮转”中作为等号右侧的输入量或系数参与关系计算，单位：不适用

$h$

在“时间片轮转”中作为等号右侧的输入量或系数参与关系计算，单位：不适用

相关概念

适用与边界

• 应用：把非抢占策略与轮转调度的时间线整理为可检查的关系、判据或算法步骤；涉及定量模型时写出公式，并说明符号、适用条件，以及需要时的单位或复杂度。
• 边界：最后只剩一项任务时，调度器可能继续运行同一项任务，不能机械地为每个时间片边界计入一次完整切换。
• 推导：C04 · 处理器调度

变量

$T$

在“首次 HTTPS 请求的首字节时间”中作为等号左侧的目标量参与关系计算，单位：不适用

相关概念

适用与边界

• 应用：把HTTP 消息、状态码与条件请求整理为可检查的关系、判据或算法步骤；涉及定量模型时写出公式，并说明符号、适用条件，以及需要时的单位或复杂度。
• 边界：因此，页面完成时间应结合实际请求序列分析，不能把单个请求的首字节时间直接当作整个页面速度。
• 推导：C05 · DNS、HTTP 与 TLS

变量

$r_{i}$

用下标 i 区分 r 的分量、样本或离散状态，单位：不适用

$t_{i}$

用下标 i 区分 t 的分量、样本或离散状态，单位：不适用

$z_{i}$

用下标 i 区分 z 的分量、样本或离散状态，单位：不适用

相关概念

适用与边界

• 应用：把随机化、指标和停止规则的实验协议整理为可检查的关系、判据或算法步骤；涉及定量模型时写出公式，并说明符号、适用条件，以及需要时的单位或复杂度。
• 边界：若删除日志只写“清除异常值”，就无法判断选择是否依赖结果。
• 推导：C02 · 数据处理与实验设计综合复习

变量

$G$

在“数据量与有效吞吐量”中作为等号左侧的目标量参与关系计算，单位：不适用

$B$

在“数据量与有效吞吐量”中作为等号右侧的输入量或系数参与关系计算，单位：不适用

$T$

在“数据量与有效吞吐量”中作为等号右侧的输入量或系数参与关系计算，单位：不适用

相关概念

适用与边界

• 应用：把有效吞吐量、重复数据与采样位置整理为可检查的关系、判据或算法步骤；涉及定量模型时写出公式，并说明符号、适用条件，以及需要时的单位或复杂度。
• 边界：两者均有用途，但比较时不能混用。
• 推导：C05 · 网络测量与故障排查

变量

$q$

在“数据页与访问代价”中作为等号左侧的目标量参与关系计算，单位：不适用

相关概念

适用与边界

• 应用：把选择率、访问代价和连接算法整理为可检查的关系、判据或算法步骤；涉及定量模型时写出公式，并说明符号、适用条件，以及需要时的单位或复杂度。
• 边界：索引选择应根据查询运算和数据类型确定，不能把一种索引的性质直接推广到所有索引实现。
• 推导：C06 · 索引与查询计划