ベスパリブ

プログラミングを主とした日記・備忘録です。ベスパ持ってないです。

Pythonのin演算子の計算量について

リスト(list)、タプル(tuple)、集合(set)、辞書(dict)にはin演算子がありますが、それぞれ計算量が違うようです。

python リスト、辞書、セット型のinを使った時の参照速度を調べてみた。 - Qiita

Python Speed - www.peignot.net

リスト(list) タプル(tuple) 集合(set) 辞書(dict)
O(N) O(N) O(1) O(1)

今まではin演算子は全部O(N)かと思っていました。

なのでforループの中にin演算子を書いたら計算量がO(NM)とかになっちゃうのが嫌で使用を避けていたのですが、集合と辞書にはin演算子使っても良さそうです。