常数次循环含数组remove操作的Python代码时间复杂度分析

待分析的示例代码 #

def example(array):
    count = 5
    for _ in range(count):
        array.remove(0)
        array.append(0)

核心疑问 #

提问者的初步判断与待明确的问题：

• 初步认知：循环上限为固定常数的for循环，本身的时间复杂度属于O(1)量级
• 待确认的困惑：循环体内的array.remove(0)操作，是否会改变整段代码的整体时间复杂度。

复杂度推导过程 #

• 先理清大O复杂度的核心判定逻辑：它只描述当输入规模n（此处即传入的array的长度）趋近于无穷大时，程序执行时间的增长趋势，所有不随n变化的固定常数系数，在最终化简时都会被忽略。
• 逐个拆解循环内两个操作的真实耗时特性：
  • array.append(0)：Python列表在尾部追加元素的操作，均摊下来是O(1)的常数耗时
  • array.remove(0)：这个操作不属于常数级开销——它需要从列表最左端开始遍历查找第一个值为0的元素，找到后还要把该位置之后的所有元素整体向前移位补位，整个过程的耗时和列表长度直接相关，基础复杂度为O(n)
• 结合循环特性计算总耗时：此处循环次数是写死的固定值5，无论传入的array长度是10个元素还是10万个元素，循环都只会执行固定轮次。单轮循环的耗时为O(n) + O(1)，5轮循环的总耗时为5*O(n) + 5*O(1)
• 按照大O化简规则省略常数系数，最终整段代码的整体时间复杂度为O(n)

常见认知误区澄清 #

不要看到循环次数是固定常数，就直接判定整段代码为O(1)复杂度。
固定轮次的循环结构本身确实是常数级开销，但如果循环体包含和输入规模n线性相关的操作，哪怕该操作只在循环里执行1次、5次，整体复杂度依然会由这个线性操作主导。举个极端例子：完全不套循环、直接写一行array.remove(0)，这段代码的复杂度也是O(n)；套个只跑5次的固定循环，本质只是把线性操作重复了固定次数，根本不会改变复杂度的量级。

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