km-trends

Edit this page

Report an issue

アルゴリズムとデータ構造2014

設問１ (a)(b)：ヒープ構造とヒープソート

ヒープ構造について

• Heap：堆積する、積み重なる
• 優先度付き待ち行列（Priority Queue）を実現する
  • ある優先度に従って、優先度の高いものから順に取り出せるコレクション
  • 出てくる順番は入れた順番に 依存しない

ヒープの計算量

要素数を $n$ とし、挿入・削除するデータを $x$ とおく。

挿入コスト

要素 $x$ を最下段に左詰めで挿入したあと、$x$ の親が自身より小さい数になるまで、$x$ と親の位置を交換していく。ヒープの高さは $\log_2 n$ 以下なので、比較・交換は最大でも $\log_2 n$ 回。よって挿入の計算量は $O(\log n)$。

削除コスト

要素 $x$ を削除したあと、ヒープの最後尾¹の要素 $p$ を $x$ の位置に移動させる。
$p$ が２つの子のいずれかよりも大きい場合、小さい方の子と $p$ を入れ替える。この操作を $p$ が２つの子より大きくなるまで繰り返す。
ヒープの高さは $\log_2 n$ 以下なので、比較と入れ替えの回数は最大でも $\log_2 n$ 回となる。よって削除の計算量は $O(\log n)$。

構成コスト

長さ $n$ の配列 $A$ からヒープを構成するとする。各要素を１つずつヒープに挿入していくときの計算量は $O(\log n)$ であるので、ヒープの構成コストは $O(n\log n)$。

解答（設問１(b)）

長さ $n$ の配列を $A$ とする。$A$ をヒープソートする手順は以下の通り。

1. $A$ をヒープ $H$ に格納する。
2. $H$ の根はヒープ中の最小値であるので、これを取り出し、結果の配列 $B$ の末尾に並べる。
3. ヒープの要素が無くなるまでヒープの再構成と根の取り出しを繰り返し、$B$ に要素を追加していく。

Step 1 のヒープの構成コストは $O(n\log n)$、Step 2 の要素の取り出しコストは $O(1)$、Step 3 のヒープの再構成コストは $O(\log n)$ である。

よって、ヒープソート全体の計算量は、
\(\begin{align*} T(n) &= O(n\log n) + n\cdot\{O(1) + O(\log n)\} \\ &= O(n\log n) \end{align*}\)

設問１ (c)：$O(n)$ のソートアルゴリズム

あらかじめ範囲がわかっている整数値については、$O(n)$ のソートアルゴリズムが存在する。

• バケットソート
• 基数ソート

バケットソート（Bucket Sort, Bin Sort）

長さ $n$ の配列を $A$ とし、$A$ の要素は $m$ 個の整数値しか取らないと分かっているとする。
このとき、$A$ にバケットソートを適用する手順は次のとおり。

1. 長さ $m$ の配列 $B$ を用意し、各要素を $0$ で初期化する。
2. $A$ を先頭から１つずつ走査し、格納されていた整数 i に対応する B[i] の値を１ずつ増やしていく。
3. 長さ $m$ の $B$ を先頭から走査し、B[i] 個ずつ i を並べてできた配列が $A$ のソート済み配列である。

計算量は Step 2 が $O(n)$、Step 3 が $O(m)$ であるが、後者は $n$ に依存しない定数である。よって、バケットソートの時間計算量は $O(n)$。

また、空間計算量は $O(m)$ であるが、$m$ が大きい場合は大規模なメモリが必要である。

バケットソートでの解答

時間計算量 $O(n)$、空間計算量 $O(90)=O(1)$

基数ソート（Radix Sort）

整数の桁ごとにバケットソートを適用することで、使用メモリを抑えたアルゴリズムを基数ソートと呼ぶ。
配列 $A$ の要素の整数が、$0,1,2,\cdots,10^k-1$ であるとする。このとき基数ソートの手順は次の通り。

1. 配列 $A$ を１の位のみで比較してバケットソートする。
2. 次に 10 の位のみでバケットソートする。
3. これを $10^{k-1}$ の位まで繰り返すと、整列済みの配列を得る。

個々のバケットソートの計算量は $O(n)$ で、これを $k-1$ 回繰り返すので、基数ソートの計算量は $O(kn)$。よって、$k$ を定数とみなせば $O(n)$ である。

また、バケットソートではバケツの数は10で良い。しかし、最悪の場合、１つのバケツに $n$ 個のデータ全てが入ってしまう。これを表現するためには、9つのバケツ同士の境目と、$n$ 個の数字を格納するスペースがあれば良い。よって、空間計算量は $O(n+9)=O(n)$²。

基数ソートでの解答

時間計算量 $O(10n) = O(n)$、空間計算量 $O(99)=O(1)$

参考

設問１

• 優先度付き待ち行列（Priority Queue）
• バケットソート
• ソートアルゴリズムまとめ
• Qiita（ソートアルゴリズム12種類）

配点例

設問１ (a)-(c)：各8点
設問２,３：各13点
（50点満点）

コメント欄（beta）

コメントはGithubレポジトリにIssueとして投稿されます。

1. 最下段・最右 ↩

2. Wikipediaの基数ソートの空間計算量「$O(nk)$」は間違っていそう。 ↩