含n--操作的嵌套循环时间复杂度及大O表示求解

无n--的情况验证 #

你说得没错：如果没有n--操作，外层循环跑n次，每次内层循环也跑n次，总操作数是n²，时间复杂度为 O(n²)。

带n--的循环拆解 #

我们先从你给出的n=5例子入手，再推广到一般情况：

n=5的执行细节 #

• 初始n=5，i=1进入外层：
  • 内层j从1开始，每次执行都会让n减1：
    • j=1：n变4，x=1
    • j=2：n变3，x=2
    • j=3：n变2，x=3
    • j=4：此时j=4 > n=2，内层循环停止
• 外层i加到2，此时n=2，i<=2成立，进入内层：
  • j=1：n变1，x=4
  • j=2：j=2 > n=1，内层循环停止
• 外层i加到3，3>1，整个循环结束
  总共有4次x++，和你观察的一致。

一般情况的时间复杂度 #

核心点在于：每次内层循环执行时，n会快速缩小，导致外层循环的后续迭代根本无法进入，内层循环的执行次数也会越来越少。

假设初始n=N，总操作次数是这样的累加：

• 第一次内层跑约N/2次，n变成N/2（向下取整）
• 第二次内层跑约N/4次，n变成N/4
• 以此类推，直到n缩小到0，循环终止

这个累加的总和是N/2 + N/4 + N/8 + ...，最终结果趋近于N，属于线性增长级别。因此带n--时，时间复杂度是 O(n)。

总结 #

• 无n--：O(n²)
• 有n--：O(n)

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