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

Question

nエレメントを挿入した後にスキップリストによって使用されるの予想されるスペースは何ですか？

私は、最悪の場合、スペース消費量が無限に増加すると予想しています。

ウィキペディアは "Space O（n）"と言っています。

これはどうやって証明できますか？

Answer 1

this thesisによると、私はより信頼性の高いウィキペディアを見つけるが、ウィキペディアは間違っているです。確率的スキップリストは、Theta(nlogn)最悪の場合の空間の複雑さです。平均PSLが合理的に行うという事実にもかかわらず

、最悪の場合に そのシータ（N LG n）が空間及びシータ（n）の時間計算量は

許容できないほど高い ありますあなたがf(n)リストの数に制限することができますので、最悪の場合は無限ではありません。f(n) = O(logn)と、この高さに達したときにコインを反転することを停止します。したがって、f(n)の完全な行がある場合、ノードの総数はO(nlogn)となるため、この場合の空間の複雑さはO(nlogn)であり、O(n)ではありません。

---

EDIT：
あなたが予想スペース消費を探して、としている場合ではない最悪として最初に、その後の質問で述べた：
はのは、下のノードとして「列」を表すとすると、すべてのノードがそのノードから「上」になります。

上記の式は、期待値の直線性のため真です。

E(#nodes_for_column_i) = 1 + 1/2 + ... + 1/n < 2（各i）。これは、確率1の場合、p = 1/2で1つのノードを持ち、これらのノードのそれぞれに余分なノードがあるためです。

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

Answer 2

我々はNと決定論skiplistを持っているのをみましょう：pはこのように私たちが導き出すことができます....、 '（= 1/4 = 1月2日、これらのそれぞれは、余分なノードの合計のp * pを）持っています'ノード。データ値に加えて、リストに含まれている：レベル1で

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

N + N/2 + N/4 + N/8 + .. N/2^k は幾何学的な進行の合計であり、その限界は2Nなので、最大メモリ消費量はN * SizeOf（Data）+ 2 * N * SizeOf（Pointer）= O （N）。

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