Cav*_*man 7 python list time-complexity slice
假设我有两个名为a和b的大小为n的列表,我想在k <n时执行以下切片设置操作
a[:k] = b[:k]
在Python wiki的Time Complexity页面中,它表示切片设置的复杂性为O(n + k),其中k是切片的长度.我无法理解为什么在上述情况下不仅仅是O(k).
我知道切片返回一个新的列表,所以它是O(k),我知道列表以连续的方式保存它的数据,所以在中间插入一个项目将花费O(n)时间.但是上述操作可以在O(k)时间内轻松完成.我错过了什么吗？
此外,是否有文档可以找到有关此类问题的详细信息？我应该查看CPython实现吗？
谢谢.
O(n + k)是平均情况,其包括必须增大或缩小列表以调整插入的元素的数量以替换原始切片.
你的情况,你用相同数量的新元素替换切片,实现只需要O(k)步骤.但是,考虑到插入和删除的元素数量的所有可能组合,平均情况必须向上或向下移动列表中的n个剩余元素.
请参阅list_ass_slice函数以获取确切的实现.
| 归档时间： |
|
| 查看次数： |
1893 次 |
| 最近记录： |