リストは配列とは異なることは理解しています。しかし、それでもO(1)ですか？これは、リスト内の要素にアクセスするのが辞書内の要素にアクセスするのと同じくらい速いことを意味しますが、これは真実ではないことは誰もが知っています。私の質問は、このドキュメント:
list ---------------------------- | Operation | Average Case | |-----------|--------------| | ... | ... | |-----------|--------------| | Get Item | O(1) | ----------------------------
そしてこの答え:
リスト内の検索は O(n) で、辞書内の検索はデータ構造内の項目数に応じて O(1) に償却されます。
最初のドキュメントが正しい場合、複雑さが同じであれば、辞書にアクセスする方がリストにアクセスするよりも速いのはなぜですか?
これについて誰か明確な説明をしてくれませんか? リスト/辞書のサイズによって常に変わると思いますが、これについてはもっと詳しい情報が必要です。
ベストアンサー1
Get item は特定のインデックス内のアイテムを取得することであり、lookup はリスト内に何らかの要素が存在するかどうかを検索することを意味します。これを行うには、リストがソートされていない限り、すべての要素を反復処理し、O(n)Get Item 操作を実行する必要があり、O(n) の lookup につながります。
辞書は、スマートなデータ構造 (ハッシュ テーブル) を内部で維持しているため、O(n)要素が存在するかどうかを確認するためにクエリを実行する必要はなく、検索につながる一定回数 (平均の場合) だけ実行する必要がありますO(1)。