如何分析含if语句的for循环函数的运行时间？附示例求解

先把你的示例函数补全（原函数缺少n参数，无法正常运行）：

def myfunc(n):
    total = 0
    for i in range(0, n):
       total += i
       if total >= n:
         return total
    return 0

核心分析逻辑 #

1. 函数行为拆解：循环从i=0开始累加，每次将i加到total中，一旦total ≥ n就立即终止循环并返回结果；仅当n=0时会循环结束后返回0。
2. 数学建模：累加的和是等差数列求和，公式为 ( S_k = \frac{k(k+1)}{2} )，其中k是循环执行的次数。我们需要找到最小的k，使得 ( S_k ≥ n )。
3. 求解循环次数：解不等式 ( \frac{k(k+1)}{2} ≥ n )，展开得到 ( k^2 + k - 2n ≥ 0 )。通过二次方程求根公式，正根为 ( k = \frac{-1 + \sqrt{1 + 8n}}{2} )。当n足够大时，这个值近似等于 ( \sqrt{2n} )，即循环执行次数为 ( O(\sqrt{n}) )。
4. 时间复杂度结论：每次循环内的累加、判断操作都是常数时间O(1)，因此整个函数的运行时间复杂度为 O(√n)。

实际案例验证 #

• 当n=10时：累加过程为0→1→3→6→10，循环执行4次，与近似值√(2*10)≈4.47的取整结果一致。
• 当n=100时：计算得k≈13.65，循环执行14次，累加和14*15/2=105≥100，符合预期。

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