algorithm - スキップ リストの時間計算量

Question

平均的なケースでスキップ リストの挿入の時間計算量が O(log n) である理由と、n 要素のスキップ リストの高さが高い確率で O(log n) である理由を教えてください。そして、各レイヤーの平均検索時間が O(1) である理由。

Answer 1

O(log n) の部分を手伝うことができます。

基本的に... [スキップリスト検索] は、配列内のバイナリ検索を非常に連想させ、おそらく、このリストでアクセスされるノードの最大数が にある理由を直感的に理解する最良の方法です。