【42生向け】cpp09-ex02 マージインサーションソートとヤコブスタール数列

この記事の目的

この記事はレビュー時のマージインサーションソートにおいてなぜヤコブスタール数列が必要になるのかの説明が簡単になるように図解する記事です。
ロジックの全てを説明するものではなく、主要な部分については省略しています。

二分探索

二分探索をすることで $2^{k-1} \leqq x \leqq 2^k - 1$ の範囲にある整数 $x$ 個の要素に要素を追加するときに $k$ 回の比較回数で挿入することができる。
要素数を比較回数の要素数効率が最もいい $2^k - 1$ にすることを維持することが前提となる。

ヤコブスタール数列とは

よく知られているフィボナッチ数の漸化式は

$$F_i=F_{i-1}+F_{i-2}$$

であり、今回のヤコブスタール数列は

$$J_i=J_{i-1}+2J_{i-2}$$

他にも色々な兄弟がいるみたいだ。

数列の種類	漸化式	スタート	数列の例
フィボナッチ数	$F_{i-1}+F_{i-2}$	0, 1	0, 1, 1, 2, 3, ...
ヤコブスタール数	$J_{i-1}+2J_{i-2}$	0, 1	0, 1, 1, 3, 5, ...
リュカ数	$L_{i-1}+L_{i-2}$	2, 1	2, 1, 3, 4, 7, ...
ペル数	$2P_{i-1}+P_{i-2}$	0, 1	0, 1, 2, 5, 12, ...
トリボナッチ数	$T_{i-1}+T_{i-2}+T_{i-3}$	0, 0, 1	0, 0, 1, 1, 2, ...

最初の挿入する要素

mainchainの要素を $a_i$ 挿入するべきsubchainの要素を $b_i$ とする
最初にmainchainと比較して挿入する要素は $b_3$ である。
比較する対象は $[b_1, a_1, a_2]$ （$2^2-1$個）であり、すでに確定している自分とpairになっている要素も追加すると $2^2$個ある。比較回数は2回となる。この要素の挿入が終わると、そこから挿入する要素のindexを1つずつ下げていって（$b_2$が残されている）高々2回の比較回数を維持する。
比較回数2回の挿入が終わると次は比較回数3回の一番indexが大きい要素から挿入をしていく。

比較回数が更新されるとき

比較回数が更新されるときの最初に挿入される要素のindexがヤコブスタール数列になる。
比較回数が更新されるとき（更新された比較回数を $k$ 回とすると）、比較されるmainchainの要素の個数は $2^k-1$ となり、挿入する要素がペアになっている要素も加えると $2^k$ 個になる。←これが重要

図の中で黄色くなっている部分が $2^k$ となる。
この黄色くなっているの右端の要素が比較回数が更新されるときに最初に挿入する要素となる。

ヤコブスタール数列が出現する

比較回数2回の最初の要素のindexを $J_{k-2}$ として、比較回数3回の最初の要素のindexを $J_{k-1}$ とすると比較回数3回の最初に挿入する要素にとって色付きの部分（これまでの挿入ですでにmainchainに属する要素たち）は先の話で $2^3$ となるべきである。

これを計算式にすると

$$J_{k-1}+J_{k-2} = 2^3$$

同じように比較回数4回の最初に挿入する要素にとって色付きの部分は $2^4$ となるべきで図のようになる。

これを計算式にすると

$$J_k+J_{k-1} = 2^4$$

これは連続する二つの項の和が公比が2の等比数列になっていることを表している。
また、漸化式を計算すると、

$$J_k+J_{k-1}=2(J_{k-1}+J_{k-2})$$

移項して

$$J_k=J_{k-1}+2J_{k-2}$$

ヤコブスタール数列が出てきた