123

inPythonの演算子の複雑さは何ですか？theta（n）ですか？

下記と同じですか？

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

Lリストです。

4

3 に答える 3

187

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

いくつかの組み込みタイプの複雑さについては、今回の複雑さのドキュメントを参照してください。

の概要は次のとおりですin。

  • リスト-平均：O（n）
  • set / dict-平均：O（1）、最悪：O（n）

セットとディクテーションのO（n）ワーストケースは非常にまれですが、__hash__実装が不十分な場合に発生する可能性があります。これは、セット内のすべてが同じハッシュ値を持っている場合にのみ発生します。

于 2012-12-14T18:20:09.793 に答える
15

それは完全にコンテナのタイプに依存します。ハッシュコンテナ（dict、set）はハッシュを使用し、本質的にO（1）です。典型的なシーケンス（list、tuple）は、ご想像のとおり実装され、O（n）です。ツリーは平均O（log n）になります。等々。これらの各タイプには__contains__、big-O特性を備えた適切な方法があります。

于 2012-12-14T18:19:24.543 に答える
-1

テストするコンテナによって異なります。これは通常、期待するものです。順序付けされたデータ構造の場合は線形、順序付けされていない場合は定数です。もちろん、ツリーのいくつかのバリアントに裏打ちされている可能性のある両方のタイプ（順序付きまたは順序なし）があります。

于 2012-12-14T18:20:15.483 に答える