Python3中list[a:b:c]的时间复杂度是否为O((b-a)/c)？

是的，list[a:b:c]的时间复杂度确实是O((b-a)/c)，或者更准确地说，等价于O(k)——这里的k是最终生成的切片的实际元素个数，和len(list[a:b:c])完全一致。

具体说明： #

• Python列表的切片操作（包括带步长的场景），核心开销在于复制选中的元素到新列表。无论是否设置步长，操作的时间复杂度都由最终需要复制的元素数量决定。
• 对于list[a:b:c]，程序会从索引a开始，以步长c跳跃选取元素，直到索引超过b为止。最终生成的切片元素个数约为(b-a)/c（整数除法取整后调整边界），因此时间复杂度和这个数量成正比，也就是O((b-a)/c)。
• 官方时间复杂度文档中提到的“获取切片O(k)”，这里的k就是切片的实际长度，带步长的情况完全符合这个结论——此时k就是len(list[a:b:c])，和(b-a)/c属于同一量级。

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