将 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) 的操作,tuple(list) 只是简单地将列表中的对象复制到元组中。因此,您仍然可以修改内部对象(如果它们是可变的),但您不能向元组添加新项。
Copying a list花费 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
关于python - 在 python 中将列表转换为元组的时间复杂度,反之亦然,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/18726969/