数据结构与算法 / 系统课时

常见增长函数比较

常见增长函数比较

前两节区分了渐进上界、下界和紧确界。本课用常见函数建立规模直觉,并解释为什么大规模的增长顺序和某个具体规模的成本比较会不同。

学习目标

  • 读懂常见增长函数的排序及其前提。
  • 用主导项或比值比较表达式。
  • 区分渐进增长、有限规模交点和真正的输入长度。

常见增长级别

对数底数固定且大于 1,nn 趋于无穷大。用 f≺gf≺g 表示 f/gf/g 趋于 0,即 f=o(g)f=o(g)。以下各相邻项都满足这种严格的渐进关系。 MIT《计算机科学的数学》渐进增长

1≺log⁡n≺n≺nlog⁡n≺n2≺n3≺2n≺n!1≺\log n≺n≺n\log n≺n^2≺n^3≺2^n≺n!

常见增长函数曲线对比

对数换底只乘一个正常数。对固定的 0<a<b0<a<b,na/nb=1/nb−an^a/n^b=1/n^{b-a} 趋于 0。对固定的 1<a<b1<a<b,an/bn=(a/b)na^n/b^n=(a/b)^n 也趋于 0。固定次幂最终慢于任意固定底数大于 1 的指数;阶乘与固定指数比较时,n!/bnn!/b^n 是因子 i/bi/b 的乘积,足够靠后的因子至少为 2,因此该比值趋于无穷大。 MIT《计算机科学的数学》常见增长

主导项与有限交点

对这些成本表达式,较低阶项的相对贡献随规模变大而下降。8n+1008n+100 属于 Θ(n)\Theta(n),3n2+20n+13n^2+20n+1 属于 Θ(n2)\Theta(n^2),nlog⁡n+50nn\log n+50n 属于 Θ(nlog⁡n)\Theta(n\log n)。要比较运行在某个规模的两个方案,还应保留常数。比如 500n500n 和 n2n^2 在正整数规模 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

在 n=2n=2 和 4 时,2n2^n 恰好等于 n2n^2。当 nn 从 8 到 16 时,n2n^2 增加到四倍,2n2^n 增加到 256 倍。有限数据帮助观察趋势,渐进关系仍需定义或极限来证明。

先确定规模代表什么

若输入是正整数 NN 的无前导零二进制编码,位数 b=⌊log⁡2N⌋+1b=\lfloor\log_2 N\rfloor+1,即 2b−1≤N<2b2^{b-1}≤N<2^b。以 NN 为上界执行 NN 轮,在数值规模中是线性轮数,在位长规模中却是指数轮数。比较方案前要统一规模和操作成本,再考虑内存与实际输入上限。 Python int.bit_length

本课练习

把 log⁡n\log n、n1.5n^{1.5}、nlog⁡nn\log n、3n3^n、n3n^3 按渐进增长从慢到快排列。下一课比较同一规模下不同输入造成的成本差异。

按自己的节奏,确认真正理解。

目录与阅读设置

阅读设置

17

记录一个想法

常见增长函数比较

0 / 10000 · 笔记保存到账号。未提交的修改会在关闭、离开或刷新后丢失。

登录哪都通