Python中tuple与list互转及list转tuple代码的时间复杂度咨询

通用转换规则时间复杂度 #

• list转换为tuple：时间复杂度为O(n)，n为原list的元素总数
• tuple转换为list：时间复杂度为O(n)，n为原tuple的元素总数

底层逻辑：Python中list和tuple是两类完全独立的序列类型，互转时会生成全新的目标容器对象，需要遍历原序列的所有元素并拷贝元素引用到新容器中，因此耗时和元素数量呈线性相关，不存在O(1)复杂度的转换实现。

具体场景问题结果 #

你给出的场景代码：
lst = [1,2,3,4]
tup = tuple(lst)
这段转换操作的时间复杂度为O(n)，其中n为原列表的长度，此场景下n=4，实际运行时仅需遍历4个元素，耗时为常数级，但从大O表示法的算法增长趋势维度，统一表述为O(n)。 #

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