Pythonの計算量について誤った認識が多いとわかったため、計算量の話をまとめたいと思います。
この記事の他には、以下の記事が良くまとまっていて自分も良く拝見しています。
計算量の話だけを記載すると上の記事の丸パクリになってしまうため、データ構造に関する周辺話題や内部実装についてお話していこうと思います。
計算量 と その周辺話題
リスト（list）
| 操作 | 平均計算量 | 最悪計算量 |
|---|---|---|
append |
$O(1)$ | $O(1)$ |
pop (末尾の要素) |
$O(1)$ | $O(1)$ |
pop (末尾以外) |
$O(N)$ | $O(N)$ |
insert |
$O(N)$ | $O(N)$ |
in |
$O(N)$ | $O(N)$ |
| random access | $O(1)$ | $O(1)$ |
random access とは, A[i] のように配列の要素にアクセスする操作です。
Pythonのリストは, 他の言語で言うArrayであり、Linked List (連結リスト)ではありません。そのためrandom accessが高速にできます。
よくある間違いがin操作の計算量です。
A = [1, 2, 3, 4, 5, 6]
5 in A
上記のような操作は, $O(N)$かかります！！！！！！！
また、Pythonのリストは要素の型が一致しなくても良いです。例えば, 以下のような配列も許されます。
A = [1, 0.0005, "1asd;kjw;qwe", True]
もしも配列の要素の型が等しく数値型の場合、array.arrayを使うと処理が高速になります。
import array
A = array.array("i", [1, 2, 3, 4])
これを使用することによって, AtCoderなどではmultisetが想定される解法の問題にて, 愚直に操作をarrayでシミュレートすることによって通るときが結構あります。
def compress(A):
B = sorted(set(A))
zipped = {}
unzipped = {}
for i, x in enumerate(B):
zipped[x] = i
unzipped[i] = x
return zipped, unzipped
def main():
import sys
readline = sys.stdin.readline
from array import array
import bisect
Q = int(input())
arr = array('i', [])
used = []
queries = []
for _ in range(Q):
query = list(map(int, readline().split()))
used.append(query[1])
queries.append(query)
zipped, unzipped = compress(used)
for query in queries:
if query[0] == 1:
x = zipped[query[1]]
bisect.insort_left(arr, x)
elif query[0] == 2:
x, k = zipped[query[1]], query[2]
ind = bisect.bisect_right(arr, x)
if ind - k < 0:
print(-1)
else:
print(unzipped[arr[ind - k]])
else:
x, k = zipped[query[1]], query[2]
ind = bisect.bisect_left(arr, x)
if ind + (k - 1) >= len(arr):
print(-1)
else:
print(unzipped[arr[ind + (k - 1)]])
if __name__ == '__main__':
main()
辞書（dict, defaultdict）
| 操作 | 平均計算量 | 最悪計算量 |
|---|---|---|
| key-valueの追加 | $O(1)$ | $O(N)$ |
pop |
$O(1)$ | $O(N)$ |
in |
$O(1)$ | $O(N)$ |
| random access (?) | $O(1)$ | $O(N)$ |
ここでいうrandom accessは以下のようなkeyアクセスのことです（ぴったりの名前がわからなかった）。
d = {1: "a", 2: "b", 3: "c"}
print(d[1])
辞書は, keyとvalueを結びつけるデータ構造で, こういうのを一般に連想配列と呼びます。
Pythonの辞書は、Hash Mapと呼ばれる方法で実装されています（以下参照）。
連想配列の実装方法は、Hash Map以外にも二分探索木などを使って実装をすることも可能です。Pythonにはないですが。
二分探索木での実装の良い点として, lower boundとかも$O(\log N)$でできることです。
Splay TreeとAVL Treeをこの前実装したので良かったら参考にしてください
面白い話題として, 以下のような辞書を考えてみましょう。
d = {True: "???", 1: "!!!!", 1.0: "aaaaaaaaaaa"}
print(d)
>>> {True: "aaaaaaaaaaa"}
Pythonの辞書ではkeyの 値が等しい (== が True) かつ ハッシュ値が等しい ときに, valueの値が更新されます. True, 1, 1.0は全て値も等しくハッシュ値も等しいので上のような上書きが発生します。
ちなみに defaultdictはdictのサブクラスで、内部実装はほぼ同じです。なので計算量は変わりません。
異なる箇所は, 存在しないkeyにアクセスしたときの振る舞いのみです。ほかは同じです。
セット（set）
| 操作 | 平均計算量 | 最悪計算量 |
|---|---|---|
add |
$O(1)$ | $O(N)$ |
pop |
$O(1)$ | $O(N)$ |
in |
$O(1)$ | $O(N)$ |
Pythonのsetの内部実装は、dictとほぼ同じです。dictのkeyのみがあるバージョンだと考えて良いと思います。
そのため計算量もdictと同じです。
ここでは最悪計算量の意味について考えてみます。このときの最悪ケースとは全てのハッシュ値が衝突してしまった場合です。
通常このようなことはほとんど起こらないようなハッシュ関数を使って実装されています。なので、ほぼ起こりませんし, 起こるような問題を故意に作るのは難しい です。
なので、よほど大きな問題サイズやよほど変なデータを扱わない限りは計算量は$O(1)$として考えて良いと思います。
両端キュー (deque)
| 操作 | 平均計算量 | 最悪計算量 |
|---|---|---|
append |
$O(1)$ | $O(1)$ |
appendleft |
$O(1)$ | $O(1)$ |
pop |
$O(1)$ | $O(1)$ |
popleft |
$O(1)$ | $O(1)$ |
insert |
$O(N)$ | $O(N)$ |
in |
$O(N)$ | $O(N)$ |
| random access | $O(N)$ | $O(N)$ |
dequeの内部実装は、双連結リストとして実装されています。そのため、先頭や末尾への要素への参照・削除・追加が高速である一方で、random accessは線形時間かかってしまいます。
Random Accessを$O(1)$でできるdequeを実装している人がいました。