時間計算量比較
横長の表が見にくいのでどうにかしたい...
以下のページをもとにPythonの時間計算量を並べた。
載っていないメソッドについては、一部を自分で補足し、自分が理解していない残りはTBC。
https://wiki.python.org/moin/TimeComplexity
https://docs.python.org/ja/3/library/
https://www.ics.uci.edu/~pattis/ICS-33/lectures/complexitypython.txt
- List:配列。現在の割り当てサイズを超えて拡張したり、先頭に近い場所に挿入/削除すると遅い。
- TupleはListと同じOperationと時間計算量を持つimmutableなデータ構造。
- Deque:双方向連結リスト＋双端。真ん中あたりのindexにアクセスすると遅い。
- Setはmutable、Frozensetはimmutableでハッシュ可。どちらも同じOperationと時間計算量を持つ。
- DictとDefaultdictは同じOperationと時間計算量を持つ。
- setのaddは末尾に追加するのわけではないけどappendに...
- dictはpython3.7以降順序も保存
- Operationに / がある場合 平均計算量/最悪計算量
- Exampleに / がある場合 類似形
- lstはリストやタプル
- Nは長さ
| Operation | List | Deque | Set | Dict | ||||
|---|---|---|---|---|---|---|---|---|
| Example | Big(O) | Example | Big(O) | Example | Big(O) | Example | Big(O) | |
| Index | l[i] | O(1) | d[0]/d[middle] | O(1)/O(N) | - | - | d[k]/d.get(k) | O(1) |
| Store | l[i] = 0 | O(1) | - | - | - | - | d[k]=v | O(1) |
| Length | len(i) | O(1) | len(d) | O(1) | len(s) | O(1) | len(d) | O(d) |
| Append | l.append(0) | O(1) | d.append()/d.appendleft() | O(1) | s.add(5) | O(1) | - | - |
| Pop | l.pop()/l.pop(i) | O(1)/O(N-i) | d.pop()/d.popleft() | O(1) | s.pop() | O(1) | d.pop(k)/d.popitem() | O(1) |
| Clear | l.clear() | O(1) | d.clear() | TBC | s.clear() | O(1) | d.clear() | O(1) |
| Slice | l[a:b] | O(b-a) | - | - | - | - | - | - |
| Extend | l.extend(lst) | O(len(lst)) | d.extend(lst)/d.extendleft(lst) | O(len(lst)) | - | - | - | - |
| Construction | list(lst) | O(len(lst)) | deque(lst) | O(len(lst) | set(lst) | O(len(lst) | dict(lst) | O(len(lst)) |
| check == | l1 == l2 | O(N) | d1 == d2 | O(N) | d1 == d2 | O(N) | s1 == s2 | O(N) |
| Insert | l[a:b]=lst | O(N) | - | - | - | - | - | - |
| Delete | del l[i] | O(N-i) | - | - | - | - | del d[k] | O(1) |
| Contain | x in l | O(N) | x in d | O(N) | x in s | O(1) | x in d | O(1) |
| Copy | l.copy() | O(N) | d.copy() | O(N) | s.copy() | O(N) | d.copy() | O(N) |
| Remove | l.remove(lst) | O(N) | d.remove(lst) | O(N) | s.remove(lst)/s.remove(lst) | O(1) | - | - |
| MinMax | min(l) | O(N) | min(d) | O(N) | min(s) | O(N) | min(d.values()) | O(N) |
| Reverse | l.reverse() | O(N) | list(reversed(d)) | O(N) | - | - | - | - |
| Iteration | for x in l: | O(N) | for dd in d: | O(N) | for x in s: | O(N) | for k, v in d: | O(N) |
| Sort | l.sort() | O(N log N) | sorted(d) | O(N) | sorted(s) | O(N) | sorted(d) | O(N) |
| Multiply | N*K | O(NK) | - | - | - | - | - | - |
| Rotate | - | - | d.rotate(i) | O(i) | - | - | - | - |
| Union | - | - | - | - | s.union(t) | O(len(s)+len(t)) | - | - |
| Intersection | - | - | - | - | s.intersection(t) | O(len(s)+len(t)) | - | - |
| Difference | - | - | - | - | s.difference(t) | O(len(s)+len(t)) | - | - |
| Symmetric Diff | - | - | - | - | s.symmetric_difference(t) | O(len(s)+len(t)) | - | - |