Python 列表/字典操作時間復雜度

#1 環境

            
              Python3.7.3

            
          

#2 List

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

#3 Dict

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

# 字典的特性

• 查找速度快,無論dict有10個元素還是10萬個元素，查找速度都一樣。而list的查找速度隨著元素增加而逐漸下降。
  不過dict的查找速度快不是沒有代價的，dict的缺點是占用內存大，還會浪費很多內容，list正好相反，占用內存小，但是查找速度慢。
• 字典值可以沒有限制地取任何python對象，既可以是標準的對象，也可以是用戶定義的，但鍵不行。不允許同一個鍵出現兩次。
  鍵必須不可變，所以可以用數字，字符串或元組充當，所以用列表就不行。
• dict的第二個特點就是存儲的key-value序對是沒有順序的！這和list不一樣。