将python列表转换为元组的时间复杂度是多少(反之亦然):
tuple([1,2,3,4,5,6,42]) list((10,9,8,7,6,5,4,3,1))
O(N)或O(1),即列表是否被复制,还是内部从可写状态切换到只读状态?
非常感谢!
这是一个O(N)操作,元组(列表)只是将对象从列表复制到元组。因此,您仍然可以修改内部对象(如果它们是可变的),但不能将新项目添加到元组。
复制列表需要O(N)时间。
O(N)
>>> tup = ([1, 2, 3],4,5 ,6) >>> [id(x) for x in tup] [167320364, 161878716, 161878704, 161878692] >>> lis = list(tup)
内部对象仍然引用相同的对象
>>> [id(x) for x in lis] [167320364, 161878716, 161878704, 161878692]
但是外部容器现在是不同的对象。因此,修改外部对象不会影响其他对象。
>>> tup is lis False >>> lis.append(10) >>> lis, tup ([[1, 2, 3], 4, 5, 6, 10], ([1, 2, 3], 4, 5, 6)) #10 not added in tup
修改可变的内部对象将影响两个容器:
>>> tup[0].append(100) >>> tup[0], lis[0] ([1, 2, 3, 100], [1, 2, 3, 100])
时序比较表明,列表复制和元组创建花费的时间几乎相等,但是由于创建具有新属性的新对象具有开销,因此元组创建会稍微昂贵。
>>> lis = range(100) >>> %timeit lis[:] 1000000 loops, best of 3: 1.22 us per loop >>> %timeit tuple(lis) 1000000 loops, best of 3: 1.7 us per loop >>> lis = range(10**5) >>> %timeit lis[:] 100 loops, best of 3: 2.66 ms per loop >>> %timeit tuple(lis) 100 loops, best of 3: 2.77 ms per loop