練習問題

アルゴリズム \(A\) の実行時間 \(T(n)\) は再帰方程式 \(T(n) = 7 T(n/2) + n^{2}\) を満たし、比較対象のアルゴリズム \(A^{\prime}\) の実行時間 \(T^{\prime}(n)\) は再帰方程式 \(T^{\prime}(n) = a T^{\prime}(n/4) + n^{2}\) を満たすという。\(A^{\prime}\) が \(A\) より速くなるのは \(a\) がどんな値のときか？

Akra-Bazzi の定理 (定理 22.4.1) を使って、次に示す分割統治型再帰方程式の漸近解 (解が満たすシータ関係) を求めよ。全ての再帰方程式で \(T(1) = 1\) であり、任意の定数 \(n\) に対して \(T(n) = \Theta(1)\) だと仮定する。Akra-Bazzi の定理における \(a_{i}\), \(b_{i}\), \(h_{i}(n)\), \(p\) の値をそれぞれ答えること。\(p\) の値は \(\log\) を使って表してよい。

• \(T(n) = 3 T( \left\lfloor n/3 \right\rfloor) + n\)
• \(T(n) = 4 T( \left\lfloor n/3 \right\rfloor) + n^{2}\)
• \(T(n) = 3 T( \left\lfloor n/4 \right\rfloor) + n\)
• \(T(n) = T(\left\lfloor n/4 \right\rfloor ) + T(\left\lfloor n/3 \right\rfloor) + n\)
• \(T(n) = T(\left\lfloor n/4 \right\rfloor ) + T(\left\lfloor 3n/4 \right\rfloor) + n\)
• \(T(n) = 2 T(\left\lfloor n/4 \right\rfloor) + \sqrt{n}\)
• \(T(n) = 2 T(\left\lfloor n/4 \right\rfloor + 1) + \sqrt{n}\)
• \(T(n) = 2 T(\left\lfloor n/4 \right\rfloor + \sqrt{n}) + 1\)

• \(T(n) = 3 T(\left\lceil n^{1/3} \right\rceil) + \log_{3} n\) (この問題では \(T(2) = 1\) とする)

• \(T(n) = \sqrt{e} T(\left\lfloor n^{1/e} \right\rfloor) + \ln n\)

ある研究チームが間違いを起こしにくいバージョンのマージソートを考案した。この奇抜なアルゴリズムはオーバーソート (over sort) と呼ばれる。

オーバーソートは次のように動作する。入力は \(n\) 個の異なる数字が並んだリストである。もしリストの長さが \(1\) なら、何もせず入力をそのまま出力する。もしリストの長さが \(2\) なら、\(1\) 回の比較を実行して出力のリストを構築する。リストの長さが \(3\) 以上なら、次のステップでソートを行う:

• 先頭の \(2n/3\) 要素からなるリストを作成し、それを再帰的にソートして \(A\) とする。

• 末尾の \(2n/3\) 要素からなるリストを作成し、それを再帰的にソートして \(B\) とする。

• 先頭の \(n/3\) 要素と末尾の \(n/3\) 要素からなるリストを作成し、それを再帰的にソートして \(C\) とする。

• \(A\) と \(B\) をマージする。重複する要素は捨てる。マージの結果を \(D\) とする。

• \(C\) と \(D\) をマージする。ここでも重複する要素は捨てる。マージの結果を出力とする。

このアルゴリズムでは数字のコピーが複数作成されるので、処理の実行者がいくつかの数字を忘れた場合でも完全なソート済みリストを正しく出力できる可能性がある。この事実がオーバーソートの利点だとチームは考えている。

1. 上記のアルゴリズムで \(n\) 個の異なる数字が並んだリストをソートするときに実行される比較の最大回数を \(T(n)\) とする。処理の実行者は決して数字を忘れず、\(n\) は \(3\) の冪だと仮定する。\(T(3)\) の値を答えよ。\(T(n)\) が満たす再帰方程式を書け。

   ヒント: 長さ \(j\) のリストと長さ \(k\) のリストを重複する要素を捨てながらマージするとき、比較は \(j + k - d\) 回実行される。ここで \(d > 0\) は重複する要素の個数を表す。

2. Akra-Bazzi の定理 (定理 22.4.1) を使って \(T(n)\) の漸近解 (解が満たすシータ関係) を求めよう。まず、Akra-Bazzi 定理を使うとき設定する必要がある次の定数の値を答えよ:

   • 定数 \(k\)

   • 定数 \(a_{0}\), \(a_{1}\), \(\ldots\)

   • 定数 \(b_{0}\), \(b_{1}\), \(\ldots\)

   • 関数 \(h_{0}\), \(h_{1}\), \(\ldots\)

   • 関数 \(g\)

   • 定数 \(p\) (対数が含まれる式を答えて構わないが、以降の問題では大まかな近似が必要になる)

3. 条件「ある \(c \in \mathbb{N}\) で \(|g^{\prime}| = O(x^{c})\)」は成り立つか？

4. 条件「全ての \(i\) で \(|h_{i}| = O (x / \log^{2} x)\)」は成り立つか？

5. 定積分を計算し、\(T(n)\) の漸近解を答えよ。

Akra-Bazzi の定理 (定理 22.4.1) を使って次の再帰方程式の漸近解 (解が満たすシータ関係) を求めよ。\(T(0) = 1\) および \(n \in \mathbb{N}\) だと仮定してよい。

1. \(T(n) = 2 T( \left\lfloor n/4 \right\rfloor) + T (\left\lfloor n / 3 \right\rfloor) + n\)
2. \(T(n) = 4 T(\left\lfloor n/2 + \sqrt{n}\right\rfloor) + n^{2}\)

3. 悪魔崇拝者協会の会員は毎週カタコンベに集い、新たな会員を迎え入れる儀式を行う。協会に参加して \(2\) 週間以上が経過した会員は毎週 \(4\) 人の新しい会員を迎え入れ、協会に参加して \(1\) 週間しか経過していない会員は \(1\) 人の新しい会員を迎え入れる。第 \(0\) 週に悪魔崇拝者は \(1\) 人しかおらず、第 \(1\) 週に悪魔崇拝者は \(2\) 人いた。

   第 \(n\) 週における協会の会員数を \(D(n)\) とする。\(D(n)\) が満たす再帰方程式を答えよ。

   再帰方程式を解く必要はない。解答には忘れずにベースケースを含めること。