list

python的列表內(nèi)部實(shí)現(xiàn)是數(shù)組（具體實(shí)現(xiàn)要看解析器, CPython的實(shí)現(xiàn) ），因此就有數(shù)組的特點(diǎn)。超過容量會(huì)增加更多的容量，set, get 是O(1)，但del, insert, in的性能是O(n)。具體的看下表，'n’是容器中當(dāng)前的元素?cái)?shù)， 'k’需要操作的元素個(gè)數(shù)

Operation	Average Case	Amortized Worst Case
Copy	O(n)	O(n)
Append[1]	O(1)	O(1)
Insert	O(n)	O(n)
Get Item	O(1)	O(1)
Set Item	O(1)	O(1)
Delete Item	O(n)	O(n)
Iteration	O(n)	O(n)
Get Slice	O(k)	O(k)
Del Slice	O(n)	O(n)
Set Slice	O(k+n)	O(k+n)
Extend[1]	O(k)	O(k)
Sort	O(n log n)	O(n log n)
Multiply	O(nk)	O(nk)
x in s	O(n)
min(s), max(s)	O(n)
Get Length	O(1)	O(1)

dict

關(guān)于字典需要了解的是hash函數(shù)和哈希桶。一個(gè)好的hash函數(shù)使到哈希桶中的值只有一個(gè)，若多個(gè)key hash到了同一個(gè)哈希桶中，稱之為哈希沖突。查找值時(shí)，會(huì)先定位到哈希桶中，再遍歷hash桶。更詳細(xì)的信息請點(diǎn)這里。在hash基本沒有沖突的情況下get, set, delete, in方面都是O(1)。自己的操作不會(huì)超過O(n)

Operation	Average Case	Amortized Worst Case
Copy[2]	O(n)	O(n)
Get Item	O(1)	O(n)
Set Item[1]	O(1)	O(n)
Delete Item	O(1)	O(n)
x in s	O(1)	O(n)
Iteration[2]	O(n)	O(n)

set

內(nèi)部實(shí)現(xiàn)是dict的。在in操作上是O(1), 這一點(diǎn)比list要強(qiáng)。
也有l(wèi)ist不存在的差運(yùn)算

Operation	Average case	Worst Case
x in s	O(1)	O(n)
Union s|t	O(len(s)+len(t))
Intersection s&t	O(min(len(s), len(t))	O(len(s) * len(t))
Multiple intersection s1&s2&…&sn		(n-1)*O(l) where l is max(len(s1),…,len(sn))
Difference s-t	O(len(s))
s.difference_update(t)	O(len(t))
Symmetric Difference s^t	O(len(s))	O(len(s) * len(t))
s.symmetric_difference_update(t)	O(len(t))	O(len(t) * len(s))