1

スキップリストから要素を挿入または削除するのにかかる時間については、少し混乱しています。

高さHのスキップリストがあり、各レベルにn / 2^iエントリが含まれているとします。
n=キーと値のペアの総数
i=スキップリストのレベルi<=H

ここで、理論に従って、挿入操作は次のアクションを実行します
。1.キー<=挿入されているキーを見つけます。
2.このキーを挿入します
。3。ベースレベルより上のレベルにこのエントリをランダムに作成します。

スキップリストがリンクリストに基づいていると仮定しましょう。
ステップ1：O（n）を取る必要があります。
ステップ2：O（1）である必要があります。
ステップ3：O（log n）時間である必要があります。私はまだこの論理で混乱しています、そしてそれは以下の質問の一部になるでしょう

質問

  1. 上記の事実に基づいて、挿入の時間はO（n）+ O（1）+ O（log n）であるべきではありませんか？低次の項を無視すると、O（n）+ O（log n）で進む必要がありますか？

  2. ステップ3でも、挿入されているキー<=キーを検索するには、O（n）時間かかり、次に挿入するためにo（1）時間がかかります。挿入の実行時間が非常に複雑になりますか？

スキップリストへの挿入にはO（log n）時間がかかると本は言っています。重要な情報が不足しているに違いありません。この概念をよく理解するのを手伝っていただけませんか。

4

2 に答える 2

1

スキップ リストは並べ替えられたデータを格納するために使用されるため、新しい要素を挿入する位置を探すときに、線形検索よりもスマートなことができます。

基本的に、より高いレベルのポインターを使用して、バイナリ検索に似たことができます。たとえば、log n - 1第 1 レベルのリンクを確認することで、新しいアイテムをリストの中間にあるアイテムと比較して、リストの前半または後半に挿入する必要があるかどうかを判断できます。次に、より精度を高めるために下位レベルのリンクを確認するたびに、このように続けます。これにより、アルゴリズムのステップ 1 の複雑さが に下がりますO(log n)。

于 2012-09-01T21:17:16.677 に答える
1

スキップ リストの要点は、アイテムを見つけるためにリスト全体を実行する必要がないことです。最初に上位リストを検索し、次にベース リストに到達するまで 1 レベル下に移動します。

一番上のリストに 2 つのアイテムが含まれているとします。最初のアイテムとその中間のどこかに 1 つです。アイテムを検索すると、リストはすでに半分になっています。各レベルでは、リストがほぼ半分になります。これが O(log n) を挿入する理由です。

于 2012-09-01T21:18:21.230 に答える