含while与for循环的算法时间复杂度计算咨询

首先咱们先把你给出的代码整理成更清晰的格式：

function(a)
    n = length(a)
    i = 1
    while i <= n
        for j = n to i+1
            print(a)
        i = i + 5

接下来咱们一步步拆解复杂度：

1. While循环的执行次数 #

你说的没错，i从1开始，每次加5，直到i > n才停止。当n足够大时，循环次数约为n/5，也就是**O(n)**级别的线性次数（常数系数在复杂度分析里可以忽略，但咱们计算实际次数时会用到）。

2. For循环的执行次数（关键！） #

这里你疑惑的点很正常，但for循环的次数并不是固定的n/5——它的次数会随着i的增大而减少，咱们得把每一轮while循环里的for次数加起来计算总和：

• 第一次while循环：i=1，for循环的j从n到2，执行次数是n - 1次
• 第二次while循环：i=6，for循环的j从n到7，执行次数是n - 6次
• 第三次while循环：i=11，执行次数是n - 11次
• ...
• 最后一轮while循环：i的取值是1 + 5*(k-1)（k是while总次数），执行次数是n - (1 + 5*(k-1))次

这是一个等差数列求和的问题：首项为n-1，末项为n - (1 +5*(k-1))，项数k≈n/5。代入等差数列求和公式：

总和 = k * (首项 + 末项) / 2

把k≈n/5代入后化简，最终的总执行次数约为n²/10——这是一个二次方级别的复杂度，也就是O(n²)。

总结 #

虽然while循环是线性次数，但每轮里的for循环次数累加起来是二次方规模，所以这段代码的整体时间复杂度是O(n²)。

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