スキップリスト(データ構造)の計算時間がO(lg n)になる?

質問

のはなぜでしょうか?
情報が少なすぎて分かりません
よろしくお願いします.

回答No.1

Yanch

質問のどの部分が分からないのか、情報量が少ないので、伝わってきませんが、

スキップリストのアルゴリズムがわからないのか、
Ｏ表記法がどういう物なのかわからないのかでしょうか。

以下、参考サイトです。

スキップリスト
http://ja.wikipedia.org/wiki/%E3%82%B9%E3%82%AD%E3%83%83%E3%83%97%E3%83%AA%E3%82%B9%E3%83%88

Ｏ表記法
http://algorithms.blog55.fc2.com/blog-entry-5.html

補足

すいません
スキップリストのアルゴリズムの動作は
ある程度理解しました.
ですが
キーの探索にかかる計算時間がO(lg n)になる理由がわかりません.

オーダーの意味については大丈夫です