リンクリストで要素を見つけるためのコストはいくらですか？O（log n）である平衡二分探索木で要素を見つけるコストは知っていますが、リンクリストはどうですか？
2218 次
1 に答える
2
リンクリスト内の要素について何も知らず、リストへのポインタがない場合、リンクリスト内の要素を検索するコストは、最良の場合はO（1）、最悪の場合はO（n）です。最良の場合、要素は最前面にあり、最悪の場合、検索している要素がそこにないことを決定する前に、すべての要素を調べる必要があります。
これは、最悪の場合の平衡二分探索木よりもはるかに遅いため、アクセスを高速化するように設計されたリンクリストにはいくつかのバリエーションがあります。たとえば、スキップリストは、複数の並列リンクリストを使用して、リスト内の要素を「スキップ」できるようにします。これには、要素をソートされた順序で格納する必要がありますが、ルックアップ時間が予想されるO（log n）まで短縮されます。
お役に立てれば！
于 2013-01-20T20:56:05.403 に答える