数据结构与算法 / 系统课时
常见增长函数比较
常见增长函数比较
前两节区分了渐进上界、下界和紧确界。本课用常见函数建立规模直觉,并解释为什么大规模的增长顺序和某个具体规模的成本比较会不同。
学习目标
- 读懂常见增长函数的排序及其前提。
- 用主导项或比值比较表达式。
- 区分渐进增长、有限规模交点和真正的输入长度。
常见增长级别
对数底数固定且大于 1, 趋于无穷大。用 表示 趋于 0,即 。以下各相邻项都满足这种严格的渐进关系。 MIT《计算机科学的数学》渐进增长

对数换底只乘一个正常数。对固定的 , 趋于 0。对固定的 , 也趋于 0。固定次幂最终慢于任意固定底数大于 1 的指数;阶乘与固定指数比较时, 是因子 的乘积,足够靠后的因子至少为 2,因此该比值趋于无穷大。 MIT《计算机科学的数学》常见增长
主导项与有限交点
对这些成本表达式,较低阶项的相对贡献随规模变大而下降。 属于 , 属于 , 属于 。要比较运行在某个规模的两个方案,还应保留常数。比如 和 在正整数规模 500 时相等。小于 500 时二次表达式更小,大于 500 时线性表达式更小。这一交点只适用于这两个成本模型。
可运行示例:看数值,也看交点
保存为 growth_functions_demo.py,用第 1 章配置的 Python 3.11 或以上解释器运行。表格是数学函数的值,并非实际运行计时。输入选为 2 的幂,方便读出以 2 为底的对数。
python
from math import log2
for n in (2, 4, 8, 16):
logarithm = log2(n)
print(f"n={n}: log2={logarithm:.0f}, nlog2={n * logarithm:.0f}, n^2={n*n}, 2^n={2**n}")
for n in (499, 500, 501):
linear, quadratic = 500 * n, n * n
winner = "equal" if linear == quadratic else "linear" if linear < quadratic else "quadratic"
print(f"n={n}: {winner}")
print("bit length of 256:", (256).bit_length())text
n=2: log2=1, nlog2=2, n^2=4, 2^n=4
n=4: log2=2, nlog2=8, n^2=16, 2^n=16
n=8: log2=3, nlog2=24, n^2=64, 2^n=256
n=16: log2=4, nlog2=64, n^2=256, 2^n=65536
n=499: quadratic
n=500: equal
n=501: linear
bit length of 256: 9在 和 4 时, 恰好等于 。当 从 8 到 16 时, 增加到四倍, 增加到 256 倍。有限数据帮助观察趋势,渐进关系仍需定义或极限来证明。
先确定规模代表什么
若输入是正整数 的无前导零二进制编码,位数 ,即 。以 为上界执行 轮,在数值规模中是线性轮数,在位长规模中却是指数轮数。比较方案前要统一规模和操作成本,再考虑内存与实际输入上限。 Python int.bit_length
本课练习
把 、、、、 按渐进增长从慢到快排列。下一课比较同一规模下不同输入造成的成本差异。
按自己的节奏,确认真正理解。