单for循环代码示例的时间复杂度为何是O(n²)而非O(n)

这是算法复杂度分析的经典易错题，错因基本都是只数显式的for循环层数，没算循环内部操作隐式带的遍历开销。

按算法备考的通用分析逻辑逐段拆解开销：

• 初始化空列表l1 = []是O(1)常数操作，对整体复杂度无影响。
• 外层循环for e in range(0, n):总共跑n轮迭代，这是复杂度计算的外层基数。
• 每轮循环里的判断条件e in range(n, 2*n)是最容易漏算开销的部分：通用场景下对线性序列做in成员判断，没有哈希、范围计算这类优化的话，需要从头到尾遍历序列逐个比对元素，直到找到目标或者遍历完整个序列，单次查询的最坏时间复杂度是O(n)。这里range(n, 2*n)对应的序列长度刚好是n，也就是说每跑一轮外层循环，就要做一次长度为n的遍历操作。
• 至于l1.append(e**3)这行，实际上永远不会执行：e的取值范围是0到n-1，和判断条件要求的[n, 2n)区间完全没有交集，这部分操作开销为0，不影响整体复杂度。

总开销计算就是n轮外层循环 × 每轮O(n)的成员检查开销 = O(n²)。

补充：实际Python3环境里对range类型做了特殊优化，x in range(...)不需要遍历序列，只要做简单的数学边界判断就能出结果，单次操作是O(1)，这种场景下整段代码实际运行复杂度是O(n)。但这属于语言层面的特定实现优化，不是这道备考题的考察范围，题目要考的就是你能不能识别出循环内部隐式的遍历操作，不要看到只有一层显式循环就直接判定是O(n)。

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