data-structures - スキップ リストの予想されるスペース消費量

Question

n 個の要素を挿入した後、スキップ リストによって使用されると予想されるスペースはどれくらいですか?

最悪の場合、スペースの消費量が際限なく増える可能性があると予想しています。

ウィキペディアには「スペース O(n)」とあります。

これはどのように証明できますか？

Answer 1

ウィキペディアよりも信頼できるこの論文によると、ウィキペディアは間違っています。確率的スキップ リストは、Theta(nlogn)最悪の場合のスペースの複雑さです。

平均的には PSL が適度にうまく機能するという事実にもかかわらず、最悪の場合、その Theta(n lg n) 空間と Theta(n) 時間の複雑さは容認できないほど高くなります

f(n)最悪の場合は無限ではありません。なぜなら、リストの数に制限できるからですf(n) = O(logn)。したがって、f(n)完全な行がある場合O(nlogn)、ノードの総数が得られるため、この場合のスペースの複雑さはO(nlogn)であり、 ではありませんO(n)。

---

編集: 予想されるスペース消費量
を探していて、質問で最初に述べたように 最悪ではない場合: 「列」を最下位ノードとして示し、そこからすべてのノードを「上」に示します。

E(#nodes) = Sigma(E(#nodes_for_column_i)) (i in [1,n]) 

上式は、期待値の直線性から成り立ちます。

E(#nodes_for_column_i) = 1 + 1/2 + ... + 1/n < 2（各 i について）。これは、確率 1 で 1 つのノードがあり、p=1/2 の場合、これらのそれぞれに余分なノードがあるためです。p'=1/2 の場合、これらのそれぞれに余分なノードがあります (合計 p*p'=1/4) ,.... したがって、次のように導出できます。

E(#nodes) = n*E(#nodes_for_each_column) = n*(1+1/2+...+1/n) < 2n = O(n)

Answer 2

N 個のノードを持つ決定論的スキップリストを考えてみましょう。データ値に加えて、リストには次が含まれます。

レベル 1 で N 個のポインター、レベル 2 で N/2 個のポインター、レベル 3 で N/4 個のポインターなど...

N + N/2 + N/4 + N/8 +..N/2^k は等比数列の合計であり、その制限は 2N であるため、最大メモリ消費量は N*SizeOf(Data) + 2*N*SizeOf です。 (ポインター) = O(N)。

レベル間リンクは考慮しませんでしたが、それらの数はポインタ数程度です。

Answer 3

予想されるスペースの複雑さ

スキップ リストにはlognレイヤーがあります。スキップ リストの各要素は、1 つまたは複数のレイヤーに表示されます。スキップ リストの予想されるスペースの複雑さを測定するために、任意の要素 x が現れるレイヤーの予想数を評価できます。

x が最下層にのみ出現する確率は 100%、最下層と 2 番目の層の両方に出現する確率は 50%、最下層の 3 層に出現する確率は 25%、出現する確率は 12.5% であることがわかっています。下の 4 層など。

数学的には、次のように x が表示されるレイヤーの予想数を表すことができます...

Sum(i / 2^(i-1)) from i=1 to logn

... ix が表示される可能性のあるレイヤーの数はどこにありますか。

直感的に、分母が分子よりもはるかに速い速度で増加するため、上記の合計が定数に収束することがわかります。これは、方程式を Wolfram Alpha に差し込むことで確認できます (n の値が非常に大きい場合、合計は 4 に収束します)。これは次のことを意味します...

[Sum(i / 2^(i-1)) from i=1 to logn] = O(1)

したがって、任意のスキップ リスト内に任意の要素を格納すると、平均して一定のスペースが必要になることがわかりました。スキップ リストに要素を格納するためのスペースの複雑さを取得するにはn、単純に を掛けnます。

n*O(1) = O(n)

このように、スキップ リストには線形の予想されるスペースの複雑性があります。

---

最悪の場合のスペースの複雑さ

これは実際にははるかに簡単です。lognレイヤーとn要素があることはわかっています。最悪の場合、すべての要素がすべてのレイヤーにあります。したがって、O(nlogn).