如何通过Big-O符号计算算法实际运行时间？附典型例题解析

首先明确推算的核心逻辑：题目已给出低阶项可忽略的前提，此时算法实际运行时间与复杂度对应的增长函数呈固定线性比例关系，不需要额外考虑低阶项、硬件差异等干扰变量。
已知基准条件：输入规模N₁=100时，对应运行时间T₁=0.5ms；待测算规模N₂=500，规模相对放大倍数为k = N₂/N₁ = 5。
通用推算公式为：T₂ = T₁ * (f(N₂)/f(N₁))，其中f(N)为对应复杂度的增长函数。

各复杂度场景下的测算结果 #

• a. 线性时间（linear，即O(N)）
  增长函数为f(N)=N，因此f(N₂)/f(N₁)=k=5
  代入计算得T₂=0.5ms *5 = 2.5ms
• b. O(N logN)
  Big-O规则中对数的底数不影响复杂度量级（底数差异属于被吸收的常数因子，不进入比例计算），因此可任选统一对数底数计算比值：
  代入f(N)=N logN，可得比例关系为：(500log500)/(100log100) = 5*(log500/log100)
  取任意统一底数计算，log500/log100≈1.35，最终整体比例≈6.75
  代入计算得T₂=0.5ms *6.75 ≈ 3.38ms
• c. 二次时间（quadratic，即O(N²)）
  增长函数为f(N)=N²，因此f(N₂)/f(N₁)=k²=25
  代入计算得T₂=0.5ms *25 = 12.5ms
• d. 三次时间（cubic，即O(N³)）
  增长函数为f(N)=N³，因此f(N₂)/f(N₁)=k³=125
  代入计算得T₂=0.5ms *125 = 62.5ms

补充说明：实际场景中如果没有“低阶项可忽略”的假设，这类比例推算会存在明显偏差——比如一个算法的实际运行时间是T(N)=0.001*N + 1000，当N=100时常数项（低阶项）占了99.99%的耗时，此时就算算法整体是线性时间，用N=100的耗时直接推导N=500的结果会完全失真，这也是仅靠Big-O标识无法精准推导实际运行时间的核心原因。

内容的提问来源于stack exchange，提问作者bpreiss12