O(n log n)复杂度下输入规模与运行时关系及规模翻倍后的运行时估算

1. 计算单位输入规模变化对应的运行时变化量 #

对于时间复杂度为O(n log n)的算法，当输入规模n足够大时，实际运行时可近似表示为：
T(n) ≈ k * n * log n
其中k是由算法实现、硬件环境等决定的常数，log n可取自然对数或二进制对数（计算比值时不影响结果）。

计算单位输入规模变化（输入规模从n变为n+Δn）的运行时变化量，步骤如下：

• 先通过已知的一组(n₀, T(n₀))数据求解常数k：k ≈ T(n₀) / (n₀ * log n₀)
• 再计算变化后的运行时T(n+Δn)：T(n+Δn) ≈ k * (n+Δn) * log(n+Δn)
• 最终运行时变化量为：ΔT = T(n+Δn) - T(n) ≈ k * [(n+Δn)log(n+Δn) - n log n]

注：若Δn远小于n，可通过微分近似简化计算：ΔT ≈ k * (log n + 1)（对n log n求导得到该式），但仅适用于Δn极小时的场景。

2. 输入规模翻倍后的近似运行时计算 #

已知输入规模n₁=10,000,000时运行时T₁=4.956秒，输入规模提升至n₂=20,000,000（即n₂=2n₁），根据O(n log n)的近似公式：
T₂ = T₁ * (n₂ * log n₂) / (n₁ * log n₁)

代入数值计算：

• n₂/n₁=2
• 取二进制对数：log₂(n₂)=log₂(2*1e7)=1 + log₂(1e7)≈1 + 23.253=24.253，log₂(n₁)=log₂(1e7)≈23.253
• 比值为：2 * (24.253 / 23.253)≈2.086
• 因此T₂≈4.956 * 2.086≈10.34秒

用自然对数验证结果一致：ln(n₂)=ln(2*1e7)=ln2 + ln(1e7)≈0.693 + 16.118=16.811，ln(n₁)=ln(1e7)≈16.118，比值为2*(16.811/16.118)≈2.086。

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