用大Θ记号比较算法效率的增长趋势

比较两个算法的效率，关键不是在某个固定输入规模下谁跑得快，而是随着输入规模增长，所需时间/资源增长得有多快。对含 n 个条目的列表，顺序搜索平均要检查 n/2 个条目（属于 Θ(n)，线性增长），二分搜索最多只需检查 log₂n 个条目（属于 Θ(log₂n)，对数增长），插入排序最坏情况需要约 (n²-n)/2 次比较（属于 Θ(n²)，平方增长）。这三类增长曲线的形状本质不同：线性增长和输入规模成正比，对数增长几乎不随规模扩大而显著增加，平方增长则会随规模扩大而急剧恶化——同一个问题，选对算法类别能决定它是”瞬间完成”还是”慢到无法忍受”，这个差距远比升级硬件带来的提速更本质。发散：大Θ记号刻意忽略了具体的比例常数和固定开销，只关心增长趋势的”形状”，这是因为当输入规模足够大时，形状的差异最终一定会压倒任何常数级别的优势——一个 Θ(n²) 算法无论常数因子多小，规模足够大后终将输给 Θ(n log n) 算法。