動的最適性予想とは？ わかりやすく解説

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2018/10/07 05:14 UTC 版)

「スプレー木」の記事における「動的最適性予想」の解説

スプレー木の性能に関しては、証明済みの定理だけでなく、最初のスレイターとタージャンの論文にも記載されていた証明されていない予想が存在する。この予想は動的最適性予想 (Dynamic optimality conjecture) と呼ばれ、それは基本的にスプレー木の性能が他の2分探索木アルゴリズムにある定数係数を加えた範囲内になるという予想である。 動的最適性予想 要素 x {\displaystyle x} にアクセスするのに、根ノードから走査してコスト d ( x ) + 1 {\displaystyle d(x)+1} かかる2分探索木アルゴリズムを A {\displaystyle A} とする。そして、 A {\displaystyle A} において、任意の木の回転を1のコストでできるとする。 A {\displaystyle A} においてアクセスのシーケンス S {\displaystyle S} を実行するコストを A ( S ) {\displaystyle A(S)} とする。すると、スプレー木が同じアクセスをするのにかかるコストは O ( n + A ( S ) ) {\displaystyle O(n+A(S))} である。 動的最適性予想には、以下のような証明されていない系が存在する。 走査予想 (traversal conjecture) 同じ要素を格納している2つのスプレー木 T 1 {\displaystyle T_{1}} と T 2 {\displaystyle T_{2}} があるとする。シーケンス S {\displaystyle S} が T 2 {\displaystyle T_{2}} において要素を前順（深さ優先順）に走査するシーケンスであるとする。このシーケンス S {\displaystyle S} を T 1 {\displaystyle T_{1}} 上で実行するコストは O ( n ) {\displaystyle O(n)} となる。 デック予想 (deque conjecture) S {\displaystyle S} が両端キュー（デック）操作を m {\displaystyle m} 回行うシーケンスであるとする。するとスプレー木上で S {\displaystyle S} を実行するコストは O ( m + n ) {\displaystyle O(m+n)} となる。 分割予想 (split conjecture) S {\displaystyle S} がスプレー木の要素の任意の順列とする。すると、 S {\displaystyle S} の順序に従って要素を削除するコストは O ( n ) {\displaystyle O(n)} である。

※この「動的最適性予想」の解説は、「スプレー木」の解説の一部です。
「動的最適性予想」を含む「スプレー木」の記事については、「スプレー木」の概要を参照ください。