时间复杂度

时间复杂度是一份计费契约，不是墙钟秒数的预测。编码决定“输入有多长”，模型决定“走一步要付多少”，最坏情况量词决定“要为哪些输入负责”。三者固定后，增长率才可跨实现比较。渐近分析可以忽略固定倍率，却不能把任意精度乘法当作常数操作，也不能用数值 $N$ 冒充写下 $N$ 所需的位数。

时间与空间复杂度公理库空间复杂度Space complexity计算在输入长度函数下使用的工作存储单元数量。衡量的资源不同：运行一步会永久增加时间计数，工作格却能擦除并复用。因此一个算法可能运行指数多步而只保留多项式数量的信息，也可能用额外存储换取更少步骤。

可复算的二分搜索界 ​

设有序数组可随机访问，一次索引和一次关键字比较都按常数计费。比较中点后，尚待搜索的元素至多为原来的一半，因此最坏比较次数满足

展开递推得到 $C(n)\le \lceil {\log }_2(n+1)\rceil$；例如 $n=8$ 时，剩余候选数可依次为 $8,4,2,1,0$，对应四次比较；只有把含中点的已检查位置移出下一轮，递推才成立。若输入只能顺序读取，定位中点本身就不再是常数操作，这个界不能原样搬过去。

编码长度与伪多项式时间 ​

若正整数 $N$ 用二进制编码，其长度为 $m=\lfloor {\log }_{2}N\rfloor +1$。执行 $N$ 次循环是 $O(N)$，但用输入长度表示就是 $O(2^m)$。因此“关于 $N$ 是多项式”并不等于“关于输入编码长度是多项式”；背包动态规划的 $O(nW)$ 界在容量 $W$ 以二进制给出时也是同一种风险。

模型边界 ​

单位代价 RAM 若允许对任意长整数一次完成乘法，会把位运算成本藏进一个步骤。位复杂度公理库位复杂度Bit complexity · Bit operation complexity固定有限编码与逐位计算模型后，以基本位操作数衡量算法成本，并将中间数的实际位长计入每次算术运算。则让加法、乘法随操作数长度收费，并累加中间数增长后的实际成本。一次 benchmark、最好情况或“典型输入很快”也都不能推出最坏渐近界；随机算法的高概率界还须给出失败概率如何随 $n$ 变化。

具体任务会换用更贴近瓶颈的模型。Word-RAM公理库Word-RAM 模型Word RAM · Word-RAM model以 w 位机器字、常数时间随机访存和明确字级操作集分析算法的随机访问机模型。按机器字操作计费，外存模型公理库外存 / I/O 模型External-memory model · I/O model · Aggarwal–Vitter model只计大小为 B 的数据块在容量为 M 的内存与外存之间传输次数的两层存储模型。统计块传输，数据流模型公理库数据流算法模型Data-stream model输入顺序到达且不能保存全文，以扫描趟数、工作空间、处理时间和输出保证评价算法。同时约束遍数与存储，Work–Depth 模型公理库Work–Depth 模型work-depth model · work-span model · computation DAG model把并行计算表示为依赖 DAG，以总工作 W 和关键路径深度 D 分离工作量与并行性。把总工作和关键路径分开。相同算法在这些模型中的数字不可脱离模型名称解释。

粗粒度复杂度理论常以图灵机公理库图灵机Turing machine通过有限控制、可读写纸带和移动读写头刻画一般算法计算能力的模型。统一编码与步数，再由预算函数定义确定性时间类公理库确定性时间复杂性类Deterministic time class · DTIME由确定性图灵机在给定时间界内判定的语言集合。。合理模型之间通常存在多项式开销的模拟，所以 P、EXP 等多项式或指数尺度的类别较稳定；线性、近线性和常数因子结论则仍然依赖具体模型。

期望运行时间变换器公理库期望运行时间变换器Expected runtime transformer · ERT calculus给概率程序逐项计费并反向组合期望成本，用几何循环算出守卫检查的额外开销，区分 ert 与 wp。把概率程序的时间当作随状态变化的成本函数反向组合。计算时须先指定赋值、采样和守卫的成本，尤其不能漏掉退出时的最后一次判断；前段输出的随机状态还可能使后段点态有限的时间具有无穷平均。