外层循环嵌套两个独立内层循环的算法时间复杂度是多少？

你的直觉是对的，这个算法的时间复杂度确实是O(n²)，第二个内层循环不会改变这个复杂度量级，具体分析如下：

• 先明确变量定义：设列表l的长度为n，即len(l) = n。
• 外层循环for i in range(len(l))会执行n次。
• 每次外层循环内部包含两个独立的内层循环：
  • 第一个内层循环for n in range(len(l))执行n次，假设内层代码是常数时间操作（O(1)），这部分每次外层循环的时间开销为O(n)。
  • 第二个内层循环for j in range(len(l))同样执行n次，内层代码也是O(1)，这部分每次外层循环的时间开销同样为O(n)。
• 总操作次数计算：外层循环执行n次，每次的总操作数是n + n = 2n，因此整体总操作次数为n * 2n = 2n²。

在时间复杂度的渐近分析中，我们只关注最高阶项，并且忽略常数系数——因为当n趋近于极大值时，常数系数对增长趋势的影响可以忽略不计。因此2n²的渐近复杂度就是O(n²)。

简单总结：只要每次外层循环里的内层循环次数都是线性的（和n成正比），哪怕有多个这样的内层循环，最终复杂度还是O(n²)。只有当内层循环的次数是n的更高阶（比如n²）、指数级（比如2ⁿ），或者外层循环次数发生变化时，才会改变复杂度的量级。

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