时间复杂度分析中的负项问题：如何简化O(n²-nk)？

首先看目标函数：

def foo(n, k):
    for _ in range(n-k):
        for _ in range(n):
            print("bar")

问题分析 #

该函数的print语句执行次数为n*(n-k) = n² - nk，疑问点在于：

• 按照大O“消除非主导项”的规则，-nk是负项，是否可以简化为O(n²)？
• 多变量场景下是否需要保留含k的项，写成O(n²-nk)？

解答 #

1. 大O表达式的基本规范
   大O表示法描述的是执行次数的渐近上界，要求表达式必须是非递减的非负函数，因此O(n²-nk)这种写法本身不规范——当k接近n时，n²-nk会趋近于0，不符合大O用来刻画增长趋势的核心目的，正确的带k的写法应该是O(n(n-k))。

2. 分场景的简化逻辑

   • 如果k是固定常数（不随n变化）：-nk属于低阶项，增长速度远慢于n²，此时主导项是n²，可以简化为O(n²)。
   • 如果k是n的函数（比如k=cn，0≤c<1）：
     • 从“上界”的角度，n(n-k) ≤ n²始终成立，所以O(n²)是合理的上界描述；
     • 如果需要更精确体现k对复杂度的影响（比如k越大，执行次数越少），可以用O(n(n-k))来描述，但这本质上是O(n²)的子集，因为n(n-k)不会超过n²。

3. 核心原则总结
   大O简化的关键是保留增长速度最快的主导项，同时确保表达式非负。带负号的项不能直接出现在大O中，多变量场景下是否保留其他变量的项，取决于是否需要体现变量间的关联对复杂度的影响——如果只需要描述最坏情况下（k最小，比如k=0）的增长趋势，O(n²)完全足够；如果需要体现k的变化带来的复杂度变化，O(n(n-k))是更精确的写法，但它依然包含在O(n²)的范围内。

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