多变量时间复杂度分析：独立与依赖变量的Big O推导疑问

场景a：m与n为独立变量 #

你的推导O(nm - m²)并不准确，原因在于Big O记号描述的是输入规模趋向无穷时的渐近上界，且需要考虑所有可能的输入组合的最坏情况：

• 当m为固定值、n趋向无穷时，T = mn - m² + m的主导项是mn，此时时间复杂度为O(n)；
• 当n为固定值、m可任意取值时，T是关于m的二次函数T(m) = -m² + (n+1)m，开口向下，最大值出现在m=(n+1)/2，此时T的量级为O(n²)；
• 若m和n同时趋向无穷且无约束，最坏情况是m取接近n/2的值，此时T的量级为O(n²)（等价于O(mn)当m与n同阶时）。

因此场景a的最坏时间复杂度应为O(n²)，而非O(nm -m²)——后者虽然是一个上界，但不是最紧的，且没有抓住独立变量下的最坏增长趋势。

场景b：m≤n的依赖变量 #

你推导的O(nm)是正确的，理由如下：

• T = m(n -m +1)，在m≤n的约束下，其最大值出现在m=(n+1)/2（当n为奇数），此时T≈(n+1)²/4，量级为O(n²)；而nm当m=n时为n²，O(n²)显然包含于O(nm)（因为nm≤n²当m≤n），所以O(nm)是合理的上界。

小输入数值矛盾的解释 #

你提到当n=5、m=5时，nm=25但实际运行时间T=5反而比m=2时的T=8小，这是因为Big O复杂度不关注小输入下的具体数值大小，它描述的是输入规模趋向无穷时，运行时间的增长速率。小输入下的数值波动是正常的，不会影响渐近复杂度的结论——当n和m都足够大时，比如n=1000、m=500，T=500*1000 -500² +500=250500，而nm=500000，此时T的量级和nm是一致的，符合O(nm)的结论。

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