如何推导函数g(n)的时间复杂度为O(n)？双重循环为何非O(n²)？

先看函数实现：

def g(n):
    s = 0 
    for i in range(n):

        # min(a,b) 返回a和b中较小的值
        for j in range(min(100,i)): 
            s = s + 1
    return s

我原本认为该双重循环的时间复杂度更接近O(n²)而非O(n)？具体来说，我的思考过程如下（针对内层循环）：

for j in range(min(100,i)):

• 当n远大于100时，我认为时间复杂度为O(n)是合理的
• 当n小于100时，我认为O(n²)的时间复杂度更合适

请问这个推理是否正确？

解答 #

大O时间复杂度描述的是当n趋近于无穷大时算法的渐近行为，核心看n足够大的情况，我们可以通过计算总操作次数来推导：

1. 分阶段计算内层循环总执行次数

   • 当i从0到99时，min(100, i)等于i，这部分总操作次数是0+1+2+...+99 = (99×100)/2 = 4950——这是固定常数，和n无关。
   • 当i从100到n-1时，min(100, i)固定为100，这部分总操作次数是100×(n-100)，是和n成正比的线性项。

2. 总操作次数的表达式
   把两部分相加，总操作次数S(n) = 4950 + 100×(n-100) = 100n - 5050。这是关于n的线性函数，根据大O定义，忽略常数项和系数，最终时间复杂度为O(n)。

3. 关于n小于100的情况
   你说n较小时总操作次数是二次的，数值上确实没错，但大O复杂度分析不关注小n的表现——当n足够小时，O(n)和O(n²)的实际运行时间差异可以忽略。我们分析复杂度的目的是预判n极大时的算法性能，所以小n的情况不影响渐近复杂度的结论。

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