Magicode logo
Magicode
6

Pythonの計算量の話

Pythonの計算量について誤った認識が多いと最近感じたのでここらへんについてまとめようと思う。

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

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

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

計算量 と その周辺話題

リスト(list

操作平均計算量最悪計算量
appendO(1)O(1)O(1)O(1)
pop (末尾の要素)O(1)O(1)O(1)O(1)
pop (末尾以外)O(N)O(N)O(N)O(N)
insertO(N)O(N)O(N)O(N)
inO(N)O(N)O(N)O(N)
random accessO(1)O(1)O(1)O(1)

random access とは, A[i] のように配列の要素にアクセスする操作です。 Pythonのリストは, 他の言語で言うArrayであり、Linked List (連結リスト)ではありません。そのためrandom accessが高速にできます。

よくある間違いがin操作の計算量です。

上記のような操作は, O(N)O(N)かかります!!!!!!!

また、Pythonのリストは要素の型が一致しなくても良いです。例えば, 以下のような配列も許されます。

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

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

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

辞書(dict, defaultdict

操作平均計算量最悪計算量
key-valueの追加O(1)O(1)O(N)O(N)
popO(1)O(1)O(N)O(N)
inO(1)O(1)O(N)O(N)
random access (?)O(1)O(1)O(N)O(N)

ここでいうrandom accessは以下のようなkeyアクセスのことです(ぴったりの名前がわからなかった)。

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

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

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

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

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

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

面白い話題として, 以下のような辞書を考えてみましょう。

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

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

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

セット(set

操作平均計算量最悪計算量
addO(1)O(1)O(N)O(N)
popO(1)O(1)O(N)O(N)
inO(1)O(1)O(N)O(N)

Pythonのsetの内部実装は、dictとほぼ同じです。dictkeyのみがあるバージョンだと考えて良いと思います。 そのため計算量もdictと同じです。

ここでは最悪計算量の意味について考えてみます。このときの最悪ケースとは全てのハッシュ値が衝突してしまった場合です。 通常このようなことはほとんど起こらないようなハッシュ関数を使って実装されています。なので、ほぼ起こりませんし, 起こるような問題を故意に作るのは難しい です。

なので、よほど大きな問題サイズやよほど変なデータを扱わない限りは計算量はO(1)O(1)として考えて良いと思います。

両端キュー (deque)

操作平均計算量最悪計算量
appendO(1)O(1)O(1)O(1)
appendleftO(1)O(1)O(1)O(1)
popO(1)O(1)O(1)O(1)
popleftO(1)O(1)O(1)O(1)
insertO(N)O(N)O(N)O(N)
inO(N)O(N)O(N)O(N)
random accessO(N)O(N)O(N)O(N)

dequeの内部実装は、双連結リストとして実装されています。そのため、先頭や末尾への要素への参照・削除・追加が高速である一方で、random accessは線形時間かかってしまいます。

Random AccessをO(1)O(1)でできるdequeを実装している人がいました。

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

Discussion

コメントにはログインが必要です。