Python列表按步长迭代的Big-O时间复杂度相关问题

问题解答 #

1. Big-O表示法的结果是O(n) #

大O表示法的核心作用是描述算法运行时间随输入规模增长的趋势，计算时会忽略所有常数系数和低阶项。不管你遍历的是1/3的元素还是全部元素，复杂度随n增长的线性趋势是一致的，所以O(n/3)和O(n)在大O规则下完全等价，统一写为O(n)。
如果你需要评估实际运行的常数时间开销，那么这个操作的实际执行步数确实和n/3正相关，比遍历全列表要快，但这不属于大O表示法的考量范围。

2. Python不会遍历整个原列表 #

Python的列表本质是连续内存存储的动态数组，支持O(1)时间的随机访问：只要知道元素的索引，就可以直接通过内存地址偏移定位到对应元素，不需要遍历前面的所有元素。
你用到的lst[2::3]切片操作，只会按规则计算出所有需要取的索引（2、5、8……），逐个取出元素生成新的子列表，整个过程只会访问n/3个元素，不会遍历整个原列表。
如果你希望避免切片生成新列表带来的额外内存开销，可以用itertools.islice实现零额外空间的按需迭代：

from itertools import islice
def function(lst):
    # 不会生成新列表，仅在迭代时实时计算索引取值
    for i in islice(lst, 2, None, 3):
        pass

这个写法的时间复杂度和切片写法一致，但是内存复杂度可以降到O(1)，更适合处理超大列表的场景。

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