単一リンクリストでのルックアップは、ヘッドポインターが与えられた場合のO（n）であることがわかっています。リンクリストの半分に常にポインタを置いているとしましょう。ルックアップ時間を改善しますか？
4 に答える
1
はい。リストの最初から開始するか、リストの途中から開始するかを決定する方法があれば、複雑さを2の定数で減らすことができます（通常、リストはソートされますが、必ずしもそうとは限りません）。ただし、これは一定の要因であるため、big-Oの複雑さの観点からは関係ありません。
Big-Oの複雑さに関連するためには、一定の要因の変更以上のものが必要です。たとえば、各半分を二等分するポインタがあり、その各半分を二分するなどの場合、線形ではなく対数の複雑さになり、「リンクリスト」を次のように変換します。 （すでによく知られている）スレッドツリー。
于 2012-01-26T17:31:11.550 に答える
0
いい考えですが、それでも検索操作は改善されません。リストのさまざまな部分にポインターがいくつあっても、リスト内の各要素を分析する必要があります。ただし、2つのスレッドを使用してリストの各半分を検索すると、理論上2倍の速度で操作できます。
于 2012-01-26T04:34:31.283 に答える
0
リンクリストのデータが並べ替えられている場合のみ。そうでなければ、他の返信ですでに述べたように。
于 2012-01-26T04:36:03.287 に答える
0
それはそうですが、漸近的にはそれでも同じです。ただし、このアイデアを使用するデータ構造があり、スキップリストと呼ばれます。スキップリストはリンクリストであり、一部のノードには、ある意味でリストの残りの部分の中央を指しているより多くのポインターがあります。このアイデアは、この画像によく示されています。この構造には通常、対数挿入の検索と削除があります。
于 2013-09-26T05:34:05.733 に答える