[解決済み] Pythonにおける*in*演算子の複雑さ

質問

の複雑さはどのようなものでしょうか？ in 演算子の複雑さは何ですか？theta(n)でしょうか？

それは次のものと同じですか？

def find(L, x):
   for e in L:
       if e == x:
           return True
   return False

L はリストです。

どのように解決するのですか？

の複雑さは in が何であるかに完全に依存します。 L が何であるかによります。 e in L になる L.__contains__(e) .

こちらをご覧ください 時間の複雑さに関する文書 を参照してください。

に関する要約は以下の通りです。 in :

• list - 平均。O(n)
• set/dict - 平均値。O(1)、ワースト。O(n)

セットとディクスのO(n)ワーストケースは非常に稀ですが、以下の場合に起こり得ます。 __hash__ がうまく実装されていない場合に起こり得ます。これは、セット内のすべてのものが同じハッシュ値を持っている場合にのみ起こります。