スキップリスト
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2025/08/07 08:14 UTC 版)
|
この項目「スキップリスト」は途中まで翻訳されたものです。（原文：en:Skip list 2006-08-23 20:43 UTC）
翻訳作業に協力して下さる方を求めています。ノートページや履歴、翻訳のガイドラインも参照してください。要約欄への翻訳情報の記入をお忘れなく。（2006年8月） |
| スキップリスト | ||
|---|---|---|
| 種類 | リスト | |
| 考案者 | William Pugh | |
| 発表年 | 1989年 | |
| 計算量（ビッグ・オー記法） | ||
| 平均 | 最悪 | |
| 空間計算量 | 
説明スキップリストはリストの階層になっている。最下層は通常のソートされた連結リストである。それより上の層は、それぞれ下のリストに対する「急行列車」のように働き、層i に存在するリストの要素は層i+1 においては固定の確率p（良く使われる p の値は 1/2 と 1/4）で存在する。各要素は平均で 1/(1-p)個のリストに属し、最も背の高い要素、つまり普通スキップリストの先頭の特別扱いされる要素はすべてのリストに属する。スキップリストは |
|
 |
この項目は、コンピュータに関連した書きかけの項目です。この項目を加筆・訂正などしてくださる協力者を求めています（PJ:コンピュータ/P:コンピュータ）。 |
このページでは「ウィキペディア」からスキップリストを検索した結果を表示しています。
Weblioに収録されているすべての辞書からスキップリストを検索する場合は、下記のリンクをクリックしてください。
全ての辞書からスキップリスト
を検索
Weblioに収録されているすべての辞書からスキップリストを検索する場合は、下記のリンクをクリックしてください。
全ての辞書からスキップリスト
を検索
- スキップリストのページへのリンク
