Python 列表/字典操作時(shí)間復(fù)雜度

#1 環(huán)境

            
              Python3.7.3

            
          

#2 List

操作	操作說(shuō)明	時(shí)間復(fù)雜度
index(value)	查找list某個(gè)元素的索引	O(1)
a = index(value)	索引賦值	O(1)
append(value)	隊(duì)尾添加	O(1)
pop()	隊(duì)尾刪除	O(1)
pop(index)	根據(jù)索引刪除某個(gè)元素	O(n)
insert(index, value)	根據(jù)索引插入某個(gè)元素	O(n) iterration
search(in)	列表搜索（其實(shí)就是in關(guān)鍵字）	O(n)
slice [x:y]	切片, 獲取x, y為O(1), 獲取x,y 中間的值為O(k)	O(k)
del slice [x:y]	刪除切片，刪除切片后數(shù)據(jù)需要重新移動(dòng)/合并	O(n)
reverse	列表反轉(zhuǎn)	O(n)
sort	排序	O(nlogn)

#3 Dict

操作	操作說(shuō)明	時(shí)間復(fù)雜度
copy	復(fù)制	O(n)
get(value)	獲取	O(1)
set(value)	修改	O(1)
delete(value)	刪除	O(1)
search(value)	字典搜索	O(1)
iterration(value)	字典迭代	O(n)

# 字典的特性

• 查找速度快,無(wú)論dict有10個(gè)元素還是10萬(wàn)個(gè)元素，查找速度都一樣。而list的查找速度隨著元素增加而逐漸下降。
  不過(guò)dict的查找速度快不是沒(méi)有代價(jià)的，dict的缺點(diǎn)是占用內(nèi)存大，還會(huì)浪費(fèi)很多內(nèi)容，list正好相反，占用內(nèi)存小，但是查找速度慢。
• 字典值可以沒(méi)有限制地取任何python對(duì)象，既可以是標(biāo)準(zhǔn)的對(duì)象，也可以是用戶定義的，但鍵不行。不允許同一個(gè)鍵出現(xiàn)兩次。
  鍵必須不可變，所以可以用數(shù)字，字符串或元組充當(dāng)，所以用列表就不行。
• dict的第二個(gè)特點(diǎn)就是存儲(chǔ)的key-value序?qū)κ菦](méi)有順序的！這和list不一樣。