渐近分析中时间复杂度log n与log(n+m)的性能及增长阶比较问题

你的说法存在两处明显问题，分维度拆解如下：

1. 平均场景下的速度结论完全颠倒 #

在默认对数底数一致、两个算法的时间复杂度常数因子相当的前提下，输入规模n、m均为正整数，因此总有n + m ≥ n。对数函数是单调递增函数，可得log(n + m) ≥ log n，运算量和时间复杂度正相关，因此log n对应的算法运行速度更快，你给出的结论刚好相反。
如果要严谨讨论平均场景表现，需要补充输入分布、m和n的取值约束，但只要二者都是正规模参数，不会出现log(n+m)更快的普遍结论。

2. 渐近同阶的结论成立有明确前提 #

你提到的极限比值为常数、属于同一增长阶的结论，仅在特定场景下成立：

• 当m是与输入规模n无关的常数，或m与n同阶（即m = Θ(n)）时，做单变量渐近分析（仅n为规模变量）：

lim(n→∞) log(n) / log(n + m) = lim(n→∞) log n / (log n + log(1 + m/n)) = 1
极限结果为正常数，此时二者确实属于同一渐近增长阶，即log(n + m) = Θ(log n)。
如果没有上述约束，该结论不成立：

• 如果m是独立于n的另一个输入规模变量，做二元渐近分析时，二者不属于同一增长阶。举个极端例子，令m = 2^n，此时log(n + m) = log(2^n + n) = Θ(n)，增长阶远高于log n，二者极限比值为0，完全不属于同一阶。

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