近況

 土曜日に妻の友達やその彼氏さんなどが我が家に集まり、パーティーをした。

はじめ自分の家に、多くの人があつまるという環境になれずだいぶ（コミュ障を克服するという意味で）葛藤があったのだが、最近はわりときちんとコミュニケーションできるようになってきたかもしれない... これも妻のおかげかな....

あとは漫画の下書きが10ページ完成したので、明日からぼちぼちペン入れをしようと思う。

アルゴリズムは、amortized analysisの復習と、van Emd Boasツリーのあたりをやっていた。

amortized analysis というのはプログラムのランタイムを図るためのアプローチで、aggregation method, accounting method などなどがある。aggregation method は単純に全体のランタイムをトータルの処理数でざっくり割る。あとaccounting methodとかはランタイムを台帳にみたてて、はじめに仮定したランタイムの合計を平均したもの？と各処理をつきあわせて、それぞれの処理が平均よりも遅ければ負債となり、早ければあまりがでるので次の処理に当てられる、みたいな方法をとる。これは、挿入と削除などそれぞれのランタイムが大きくばらついている時に近似値をみるときにいいらしい。まあそういうざっくりした理解なのであやういが。。。。

van Emde Boas ツリーは　ノード全体（横に一列にならんだレイヤー）の総数を　2^2k みたいな感じで２の階乗として　u を定義する。その u ^1/2 を　そのレイヤーへのポインタの総数とする。みたいなことをする。つまりはじめに定義されたレイヤー（あたいには 1, 0 しか入らない）に対してポインタとしてのツリーを superimposition するわけだ.

いろいろ態様があるのでここで一括して述べるのは控えるが、 van Emde Boasの中でも階層が２以上あるやつの場合の sucessor やpredecessorを求めるアルゴリズムは比較的単純で、まず葉ノードから上に上がっていって上がっていってる方向の逆の子ノードが１になったときに下に降りていき、その際は右の１を再帰的に探していくか、左のそれを探していく。

階層が２だけのツリーの場合ブロック単位で検索したりできるのとやはり階層が低いのでアドバンテッジがありそうである。

そろそろ嫁に怒られるので今日はここまで