内层从外层迭代值i起始的双重循环Big O时间复杂度是多少

• 你给出的这段双层循环结构，时间复杂度仍然是O(n²)，内层循环从i值起始的设计不会改变其平方级的渐近复杂度。

复杂度计算逻辑 #

我们默认循环体内执行的都是常数时间O(1)的操作，直接统计所有循环的总执行次数即可：

1. 外层循环的变量i从0遍历到n-1，总共执行n轮迭代
2. 对每一轮固定的i值，内层循环变量j从i遍历到n-1，单轮内层循环的执行次数为n - i次
3. 把所有轮次的执行次数累加，总操作数是标准的等差数列求和：

   n + (n-1) + (n-2) + ... + 2 + 1 = n*(n+1)/2 = 0.5n² + 0.5n

大O表示法的核心规则是只保留表达式中的最高阶项，忽略所有低阶项、固定常数系数，因此上述总操作数化简后最高阶为n²项，对应时间复杂度就是O(n²)。

常见认知误区 #

很多新手会误以为内层循环必须每次跑满n次才算O(n²)，这是对大O定义的误解：大O衡量的是运行时间随输入规模n增长的量级趋势，哪怕二次项的系数是0.5，当n足够大时，线性项、常数项对增长趋势的影响可以完全忽略，只要总执行次数是关于n的二次多项式，这类结构都属于O(n²)的复杂度范畴。

你给出的参考示例代码如下：

for i in range(n):
  for j in range(i, n):
    # 循环内为常数时间操作

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