某競技プログラミングコンテストにて、要素群の中に特定の要素が入っているかを判定する処理を実装しなければならない問題がありました。
この問題では、なにも工夫せずリストで実装すると指定された実行時間以内にプログラムが終了しません。
リストを使う方法(イメージ)
A=[1,2,3,4,5,6,7,8,9,10]
if 5 in A:
print("YES")
このように実装して、要素が少ない時は問題にはならないですが、要素がとても多いときは実行時間が長くなり、競技プログラミングのコンテストではタイムオーバーになってしまう。ちなみに計算量はO(n)。
では、どうしたら良いのか。
リストを使うのではなく、set型を使えば高速化できる！
setを使う方法
A={1,2,3,4,5,6,7,8,9,10}
if 5 in A:
print("YES")
このようにするだけで劇的に速くなるそうです。計算量はO(1)に。
setの使い方は以下のページ
https://docs.python.org/ja/3/library/stdtypes.html#set
参考