Navarro本

スターリングの近似(Stirling's approximation)

2.1 Worst-Case Entropyでスターリングの近似が紹介されています。 その後、2.3.1 Bit Sequencesにて以下のような等式が出てきます。 これに関して we used Stirling's approximation と書いてあるのですが、どこがだよ感がすごい。 スターリングの近似はNav…

順序木のバイナリ表現、あるいは括弧表現

2.1 Worst-Case Entropyにnノードの順序木は2nビットで表現できると書いてあります。 これは深さ優先探索をして、ノードに入る時に 1 を、出る時に 0 を出力することで実現できます。各ノードに対して入る時と出る時にビットが出力されるので2ビット、これが…

カタラン数(Catalan Number)

2.1 Worst-Case EntropyにnノードのGeneral Ordinal Trees(一般順序木?)(一般じゃない順序木とは)の種類はn-1番目のカタラン数になるということが書いてあります。 Wikipediaの「()を正しく並べる方法」というのがそれに相当するもの(のはず)。 そ…

Navarro本を読んでいく

Gonzalo NavarroのCompact Data Structuresを読んで気になったことを書いていきます。 Rustによる実装もやっていく予定です。