竞争分析

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

消歧 ​

近似比通常比较完整输入上的可行解与最优解；竞争比还要衡量未来不可见的代价。两者都必须说明目标与比率方向，最大化问题不能照搬这里的最小化不等式。$OPT=0$ 时，成本不等式仍有意义，直接相除却没有意义。

资源增广理路资源增广Resource augmentation · Resource-augmented competitive analysis在同一请求序列与成本目标下，给在线算法更多指定资源，再与较少资源的离线最优比较的方法。比较不同资源下的 ALG 与 OPT，例如在线分页给更大缓存；这不是原竞争比的直接改进，必须把两侧资源写进符号。经验 workload 上的平均比率也不是对所有序列的竞争保证。

租买问题的完整阈值计算 ​

每天租金为 $1$，买断价为整数 $B\ge 1$；不知道总共会用多少天 $d\ge 1$。算法前 $B-1$ 天租用，若第 $B$ 天仍有需求，就在当天开始前买断。若 $d<B$，在线与离线都付 $d$；若 $d\ge B$，在线付 $(B-1)+B=2B-1$，离线一开始买，只付 $B$。因此对每个季节均有 $ALG\le (2-1/B)OPT$，且不需要加性常数。

例如 $B=5$：只用三天时付 $3$；恰好用五天时，前四天租金 $4$ 加买断 $5$，共付 $9$，离线付 $5$。最难的是需求恰好持续到买断那天，继续使用更久不会再增加在线成本。若先租满五天再买，最坏比率会变成 $2$；阈值的端点和当天是否重复计费直接影响精确常数。

量词与随机对手 ​

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

Yao 型下界论证先选一个输入分布，再证明每个确定算法在该分布下的期望成本都足够大，最后与该分布下离线最优的期望成本比较。在适用的极小极大条件下，这能推出随机算法的最坏输入下界。应明确比较的是期望成本之比还是随机比率的期望；当 $OPT$ 随实例变化时，二者一般不同。

势函数逐轮证明 ​

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

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

与遗憾界的比较 ​

External regret理路遗憾与比较器类Regret · Comparator class用累计损失相对预先规定的比较器类最优值来评价在线决策。通常比较累计损失的加性差，基准是在整条损失序列结束后选出的最好固定动作。“固定”指该动作在这一条序列内不随轮次切换；换一条序列，最佳动作当然可以改变。租买问题中，买断会永久改变后续成本和可用状态，离线基准按完整使用天数选择租买方案。因此它与普通无状态 experts 模型的区别在于状态、比较器类别和乘法／加法评价方式，不能用“最佳方案会随序列改变”来区分。