Pythonの計算量の話

Pythonの計算量について誤った認識が多いとわかったため、計算量の話をまとめたいと思います。


この記事の他には、以下の記事が良くまとまっていて自分も良く拝見しています。

https://qiita.com/Hironsan/items/68161ee16b1c9d7b25fb

計算量の話だけを記載すると上の記事の丸パクリになってしまうため、データ構造に関する周辺話題や内部実装についてお話していこうと思います。


# 計算量 と その周辺話題
## リスト（`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`操作の計算量です。
```python
A = [1, 2, 3, 4, 5, 6]
5 in A
```
上記のような操作は, __$O(N)$かかります！！！！！！！__


また、Pythonのリストは要素の型が一致しなくても良いです。例えば, 以下のような配列も許されます。
```python
A = [1, 0.0005, "1asd;kjw;qwe", True]
```

もしも配列の要素の型が等しく数値型の場合、`array.array`を使うと処理が高速になります。
```python
import array

A = array.array("i", [1, 2, 3, 4])
``` 

これを使用することによって, AtCoderなどでは`multiset`が想定される解法の問題にて, 愚直に操作を`array`でシミュレートすることによって通るときが結構あります。

https://atcoder.jp/contests/abc241/tasks/abc241_d

```python:嘘解法だけど通る.py
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アクセスのことです（ぴったりの名前がわからなかった）。
```python
d = {1: "a", 2: "b", 3: "c"}
print(d[1])
```

辞書は, keyとvalueを結びつけるデータ構造で, こういうのを一般に連想配列と呼びます。

Pythonの辞書は、Hash Mapと呼ばれる方法で実装されています（以下参照）。

https://wa3.i-3-i.info/word11931.html

連想配列の実装方法は、Hash Map以外にも二分探索木などを使って実装をすることも可能です。Pythonにはないですが。
二分探索木での実装の良い点として, `lower bound`とかも$O(\log N)$でできることです。

`Splay Tree`と`AVL Tree`をこの前実装したので良かったら参考にしてください

https://github.com/Hidestament/Algorithms-DataStructures/tree/main/DataStructures/BinarySearchTree


面白い話題として, 以下のような辞書を考えてみましょう。
```python
d = {True: "???", 1: "!!!!", 1.0: "aaaaaaaaaaa"}

print(d)
>>> {True: "aaaaaaaaaaa"}
```

Pythonの辞書では`key`の __値が等しい (== が True)__ かつ __ハッシュ値が等しい__ ときに, `value`の値が更新されます. `True, 1, 1.0`は全て値も等しくハッシュ値も等しいので上のような上書きが発生します。



ちなみに `defaultdict`は`dict`のサブクラスで、内部実装はほぼ同じです。なので計算量は変わりません。
異なる箇所は, 存在しない`key`にアクセスしたときの振る舞いのみです。ほかは同じです。

https://docs.python.org/ja/3.6/library/collections.html



## セット（`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`を実装している人がいました。

https://prd-xxx.hateblo.jp/entry/2020/02/07/114818