MIT Open course: Introduction to Algorithmsのまとめ(12〜14回)
データ構造2、特殊なリスト
◆skip lists
◯特徴
・複数のsorted linked listを用いた、シンプルで効率的な動的探索データ構造
・小田急線みたいな感じ。各駅停車リスト、準急リスト、急行リスト、快速急行リストがあって、例えば、各停も準急も止まる駅では乗り換え可能。新宿から目的の駅まで電車を乗り継いで早く行く。
・n駅あるとき、各駅停車はn個、準急n/2駅おき、急行はn/2^2おき、...というようにlogn種類の電車があるように設計する
・binary searchと似ている
・挿入は、まず各停に駅を追加し、コインを振って表が出たら準急に止まるように、もう一度コインを振って表が出たら急行に駅を追加し、...を繰り返して、裏が出たら追加せずに終了する。
・探索は、With high probability(w.h.p.)でO(logn)で到着できる。
(証明)逆向きに考える(ゴールからスタートにいく)
①w.h.p 種類＝O(logn)←種類がclogn以上となる確率はn回ともclogn回連続でコインが表(ブールの法則)ノ確率より小さい
②w.h.p 合計移動数<=clogn種類の電車を出すのに必要な、コインを降る回数=O(logn)
◯With high probability(w.h.p.)の定義
・イベントEが1-O(1/n^α)ノ確率で起きるようなαが存在する。
(w.h.pに関する証明は、背理法で攻めることが多い)
◆償却分析
◯特徴
・あるsequenceに対して、一部の操作のコストは非常に大きいが、操作の平均コストは小さいことを示す分析→結局平均してどれくらいのコストが必要なのかを知る
◯解析方法
A)aggregate 総計法?
合計を求めて、平均のコストを算出
B)accounting 課金法?
「償却原価」\hat{c}_iを払い、余ったときは銀行に預けて足りないときに使う
「銀行残高」は正であるべき(コストが不足してはダメ)
C)potential ポテンシャル法
・「銀行残高」を物理のポテンシャルエネルギーのように考える。
・i回目の操作後のデータ構造D_iとして、
定義)Φ:{D_i}→実数 such that Φ(D_i)=0,Φ(D_i)>=0 for all i
・「償却原価」\hat{c}_i=c_i+Φ(D_i)-Φ(D_{i-1})
注)accounting methodとpotential methodは表裏一体の関係。「償却原価」を先に定義するか、「銀行残高」を先に定義するか
◯例題,動的テーブル
・全データ数がわからないときに、ハッシュテーブルを動的に生成する方法
①テーブルをnewする(古いテーブルの二倍の大きさ)
②古いテーブルからデータをコピーする
③古いテーブルを捨てる
・データ数nで、n回insertを行う
・コストc_iは、1,2(=1+2^0),3(=1+2^1),1,5(=1+2^2),1,1,1,1,9(=1+2^3),1,...
◯例題の解析
A)aggregate
合計コスト=1*n+��^{floor(log(n-1))}2^j<=3n=Θ(n)
平均コスト=Θ(n)/n)=Θ(1)
B)accounting
\hat{c}_i=3として、実行すればうまくいく
C)potential
Φ(D_i)=2i-2^{ceiling(logi)}とすれば、\hat{c}_i=3が導かれる
◆competive analysis
◯定義
・オンラインアルゴリズムAがα-competitiveであるとは、「どんなsequenceSに対しても、cost_A(S)<=αcost_opt(S)+kとなるkが存在すること」
・入力列Sについての仮定はない
◯例題,自己組織リスト
・操作Access(x)のコストはrank(x)(先頭からの距離)
・入れ替えの操作のコストは1
・目的は、「アクセスコストと入れ替えコストの総和を最小化すること」
◯MTF(Move To Front)による例題の解析
・xにアクセスの後に、xを先頭に持ってくるというsimpleなヒューリスティック
・MTFは4-competitive!
(証明概要)
・Φ(L_i)=2|{x,y},x<(L_i) y & y <(L_i*) x|→二つのリストの各要素の前後関係がどれだけ食い違っているかを定義し、償却コストの上限を求め、総コストの上限を求める。
今回でデータ構造終了。
一番面白かったのは、skip listかな。実際の電車は駅の利用者数とかで急行が停まる駅とか決めてるだろうけど、効率だけ考えると、実は停まる駅も電車の種類も最適化されるなんて。。かっこえーーー。
そして、そのデータ構造を決定するのも、これまたRANDOMNESS。
今まで、RANDOMNESSというものに全く意識はなかったけど、アルゴリズムで最悪ケースをなくすときとかにめちゃくちゃ有用なんだということに気づいた。クイックソートも然り。ハッシュも然り。すごい。
competive analysisは先生が"amazing"と違っていただけあってなかなかきれい。入力によらず最適な方法のコストのα倍以下であることが保証される。
証明のΦの選び方とか、計算方法はどこかで見たことがある気がするが何だろう。まぁ美しい!
次もがんばろう。
