循环时间复杂度计算疑问：多操作与嵌套场景下的复杂度判定

先搞懂：什么时候相加，什么时候相乘 #

• 相乘：当代码是嵌套依赖执行时——比如外层每跑一次，内部的操作都要完整执行一轮，这时候总复杂度是「外层操作的执行次数 × 内层单次操作的复杂度」。
• 相加：当代码是顺序独立执行时——比如做完A操作再做B操作，总复杂度是「A的复杂度 + B的复杂度」，最终取最高阶的项（时间复杂度只看主导项）。

代码示例1分析 #

while var in arr:
    arr.remove(var)

假设arr初始长度为n，拆解每一步的复杂度：

1. var in arr：列表的成员判断是O(n)，因为要逐个遍历元素匹配。
2. arr.remove(var)：找到元素后，删除操作需要把该元素后面的所有元素往前移动一位，平均复杂度也是O(n)。

循环的执行次数：最坏情况是arr里全是var，这时候循环会执行n次（每次删一个，直到列表为空）。每次循环里的两个操作是顺序执行，所以单次循环的复杂度是O(n)+O(n)=O(n)。总复杂度就是「循环次数 × 单次循环复杂度」= n × O(n) = O(n²)。

即使每次循环后列表长度减少，求和计算的话是n + (n-1) + (n-2) + ... + 1 = n(n+1)/2，这个结果的主导项还是n²，所以时间复杂度依然是O(n²)。

代码示例2分析 #

for i in range(n):
    arr.remove(var)
    arr.remove(var1)

外层循环固定执行n次，每次循环里有两个remove操作：

1. 每个arr.remove()的复杂度是O(m)（m是当前列表的长度），最坏情况下每次删除都需要移动大量元素，复杂度仍为O(n)级。
2. 两个remove是顺序执行，所以单次循环的复杂度是O(n)+O(n)=O(n)。

总复杂度是「循环次数 × 单次循环复杂度」= n × O(n) = O(n²)。

哪怕每次循环后列表长度减少2，求和计算的结果主导项依然是n²，所以最终时间复杂度还是O(n²)。

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