竞争分析

在线算法付出的额外成本来自信息延迟，而不是计算不够充分。竞争分析让 ALG 与预知整个请求序列的 OPT 在同一序列上结算，由乘法常数刻画“看不见未来”的最坏代价；固定加性项只吸收初始状态等一次性差异，不能随序列变长。

消歧 ​

近似比比较同一完整输入上的可计算解与 NP 优化最优；竞争比还受未来不可见限制。Regret 是加性差且常与固定动作比较。最大化问题比率方向需改写，OPT 为零也要处理。

资源增广比较不同资源下的 ALG 与 OPT，例如在线分页给更大缓存；这不是原竞争比的直接改进，必须把两侧资源写进符号。经验 workload 上的平均比率也不是对所有序列的竞争保证。

量词与随机对手 ​

确定性定义先固定算法，再要求对每个序列不等式成立。随机算法面对 oblivious 对手时，先固定序列 $\sigma$，再取 ${\mathbb{E}}_{r}AL{G}_r(\sigma )$；adaptive 对手可按历史动作选请求，序列本身依 $r$，不能使用同一交换顺序。

Yao 原理为随机下界选择一个输入分布，证明每个确定算法在该分布下期望比率大；它不给随机算法上界，也不能把单个最坏序列分布化后直接使用。

势函数逐轮证明 ​

Paging/LRU 一类证明可设势衡量 ALG 与 OPT 缓存差异，逐请求验证

求和后中间势消去，若 $0\le {\mathrm{\Phi }}_T$ 且初势有界，得到加性常数。势函数依两个算法状态，这与只分析一个结构操作序列的摊还势不同。

短序列和加性常数 ​

若初始装载需固定成本，严格比率在 $OPT=0$ 的短序列上无定义；$\beta$ 吸收该差，但必须与序列长度无关。写成 $ALG\le (c+o(1))OPT$ 的 asymptotic 版本也要说明极限按 $OPT\to \mathrm{\infty }$。

三类比较基准 ​

Approximation ratio 给算法完整实例仍受计算限制；competitive ratio 与知道未来的离线 OPT 比；regret 通常与最好固定动作做加性比较。Ski rental 的 OPT 每序列可选租或买，不是一个固定动作跨全部序列，因此也不是普通 experts regret。