如何判定Python代码的正确时间复杂度？以下代码是n²还是n³？

时间复杂度判定通用规则 #

• 先将代码拆分为独立执行的代码块，分别计算每个块的时间复杂度，最终整体复杂度取所有块中的最高量级
• 不能仅通过循环层数判定复杂度，需额外注意循环内部的操作本身的时间复杂度：Python中不少内置操作并非O(1)时间消耗
• 计算时忽略常数项、低阶项，仅保留最高阶的量级作为最终结果

示例代码复杂度结论 #

你提供的代码时间复杂度为O(n³)，认为是O(n²)的结论是错误的。
示例代码如下：

n=int(input())
L=[]
for i in range (n):
    for j in range (n):
        L.append(i*j)
for i in range (n):
    l=L[:]+[i]

逐块复杂度分析 #

1. 两层嵌套循环块
   这部分复杂度为O(n²)：两层循环各执行n次，append是均摊O(1)的操作，累计执行n²次操作，执行结束后列表L的长度为n²。
2. 后续单层循环块
   这部分复杂度为O(n³)，是拉高整体复杂度的核心：

• 外层循环共执行n次
• 每次循环内的L[:]是列表全量切片复制操作，时间复杂度和L的长度成正比，当前L长度为n²，因此单次切片操作复杂度为O(n²)
• 后续的列表拼接操作+[i]的时间复杂度同样和L长度正相关，为O(n²)
• 该块总复杂度为n * O(n²) = O(n³)

整体代码复杂度取最高阶量级，最终为O(n³)。

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