python两种内置数据类型(列表list和字典dict)上各个操作的大O数量级
python两种内置数据类型(列表list和字典dict)上各个操作的大O数量级
1.对比list和dict操作
2.list列表数据类型常用操作性能
(1)按索引取值和赋值(v=a[i],a[i]=v)
由于列表的随机访问特性,这两个操作执行时间与列表大小无关,均为O(1)
(2)列表增长,可以选择append()和“+”
list.append(v),执行时间是O(1)
lst=lst+[v],执行时间是O(n+k),其中k是被加的列表长度。
3.dict字典数据类型常用操作性能
字典与列表不同,根据关键码(key)找数据项,而列表是根据位置(index)。
最常用的操作取值get和赋值set,其性能均为O(1);另一个重要操作contains(in)是判断字典中是否存在某个关键码(key),这个性能也是O(1)
python官方的算法复杂度网站
https://wiki.python.org/moin/TimeComplexity