关于O(n log n)算法10倍输入规模计算结果的疑问

你的计算错误源于误用了对数的运算法则：你把log(10n)错误拆成了log10 * logn，但正确的对数乘法法则是log(ab) = loga + logb（底数相同的前提下）。

正确的推导过程应该是：

(10n * log(10n)) / (n * logn) = 10 * (log(10) + logn) / logn = 10 * (1 + log(10)/logn)

书中给出的34是基于近似计算的结果：

• 若使用自然对数（ln），ln10≈2.302，当原输入规模n满足lnn≈1（即n≈2.7），代入得10*(1+2.302)=33.02，近似为34；
• 若使用以2为底的对数，log₂10≈3.32，当log₂n≈1.5（即n≈2.8），代入得10*(1+3.32/1.5)≈32.13，同样近似为34。

简单来说，你错在对数拆分的步骤，把加法当成了乘法，这才导致结果和书中不符。

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