第 7 回 下限

本日の内容

ここでは解決にかかる最小の時間がわかっている問題を取り上げます。

7-1. 計算量の下限

問題を解くのにかかる最小の手数を求めるのは困難で、 ほとんどの問題でわかってません。 ここでは Knuth が示した Sorting の比較の下界について述べます。

計算時間を示す関数の増加の仕方を下から抑えるには Ω による オーダー表記を使います。 f(n) = Ω(g(n)) とは、 fの増え方は少なくともg程度を意味し、ある意味 f≧g のような意味を持ちます。 この記号の厳密な定義は次の通りです。

「ある数 c>0 と N0 が存在し、全 ての N0 より大きい数 N に対して f(N)≧cg(N) が成り立つ」。 なお、これは一階述語論理式では次のように書けます。
(∃ c>0, N0) ( ∀ N≧N0) [f(N)≧cg(N)]

7-2. Sorting

与えられた数列を小さい順(大きい順)に並べ換えて出力する問題を Sorting と言うことにします。

最悪計算量がもっとも良い Sorting アルゴリズムとしてヒープソートを紹介 します。 但し、平均的な問題に対して、実際に計算機にプログラムを与え動かすと、ヒー プソートよりクイックソートの方が速くソートできるようです。

クイックソート

順序木とは、二分木において、頂点の大小関係が左から右にならんでいること を言います。 根から見ると、左の子の頂点やその下の子の頂点の値全ては根の値より小さく、 反対に右の頂点やその下の子の頂点の値全ては根の値より大きいです。

クイックソートは与えられたデータの列をこの二分木にはめ込むように列を整 列させます。 クイックソートで使われる partition(s, t) という 関数は次のような処理をします。なお、この s, t と いう変数は s 番目から t 番目までのデータに着目す ることを意味します。

  1. s=t なら停止します。
  2. s<t の時、以下を実行します。 根となる頂点の値を s 番目から t 番目のデータ の中から選びます。
  3. 選んだデータより小さい値を前方へ、選んだデータの値以上の値を後方へ 移動させます。そのため、与えられた列を前方、後方の両方から見ていきま す。 選んだデータに対して、前方に行くべきデータと、後方に行くべきデータの両 方を見つけたら交換するようにします。
  4. 選んだデータの値より小さい値と、そうでない値の境界が r 番目になったとします。その時、再帰的に partition(s,r) と partition(r+1,t) を行います。

この処理により、順序木の左に置かれるデータと右側に置かれるデータを区分 されます。そして、要素一つになるまで区分を繰り返すことにより、与えられ たデータが整列されることになります。 partition関数の実行時間は与えられたデータを全て読むので O( t - s) に なります。 もし、都合良く順序木が完全二分木になってくれれば実行時間は次のようにな ります。

O ( n ) + 2 O LRparen{frac{ n }{2}} + 4 O LRparen{ frac{n}{4}} + ... + n O( 1 )
= sum{i = 0}{log n} 2^i O LRparen{ frac{n}{2^i}}
= O ( n log n )

しかし、与えられたデータ全てが等しいときなどは完全二分木にならず、一直 線の形の木になってしまうので、実行時間は次のようになります。

O ( n ) + LRparen{1 + O ( n-1 )} + LRparen{1 + O ( n-2 )} + ... + LRparen{1 + O ( 1 )}
= sum{i = 0}{n-1} LRparen{ 1 + O ( n - i)}
= O ( n ^ 2 )

ヒープソート

ヒープと言うデータ構造は木構造において親は子より常に大きいという条件を 満たすものです。 そのため、最大値は根に配置されることになりますが、他の頂点上の値は気の 左右どちらにも置くことができるという任意性があります。 また、データの数や値に関わらず、常に完全二分木に保つことが可能になりま す。 木の頂点数を n で表すと、 木構造を完全二分木に保てるため、以下で説明するようにデータの挿入と、根の 値の削除を 共に O( log n ) で行うことができます。 データの挿入は次のようにします。 完全二分木を保つように頂点を一つ追加し、親となる頂点と値を比較し、親よ り大きい場合だけ親の値と交換していきます。 根にたどり着くまでに O( log n ) 頂点しかありませ んので、この処理をO( log n ) 回繰り返すとヒープの条件を満たす完全二分木を作ることができます。 一方、根の値の削除は次のようにします。 完全二分木を保ったままで削除可能な頂点に着目します。 根の値を取り除き、その頂点を削除し値を根に配置します。 そして、その頂点の値と新しく子になった二つの値から最大値を求めます。 その時、親が最大になるために値の交換が必要なら交換します。 交換した場合、交換した先で同様の変更をします。 これを交換が必要なくなるまで繰り返すと ヒープの条件を満たすことになります。 このようにすると、交換するたびに木を根から葉へとたどりますから、高々木の高さ O( log n ) 回の交換で済みます。

ヒープソートはこの考え方を利用して、 (1)与えられたデータをもとにヒープを作り (O( n log n ) ステップ) (2)できたヒープから根をどんどん取り出していく (O( n log n ) ステップ) ことで大きい順にデータを取り出すアルゴリズムです。 ヒープは完全二分木なのでどのような入力の配列に関しても計算時間が大きく 変化しません。さらに完全二分木という性質を利用して、配列において i 番目の頂点の子を2i、2i+1 とすること で再帰処理を使わずに済みます。従って、繰り返し処理だけでソーティングが できる点もクイックソートと異なります。

7-3. Sorting の比較の数

ここでは、比較をすることだけで並べかえをする時、必要な比較の 回数を求めます。

ここで注意が必要なのは、 Sorting を行うプログラムには比較以外の手法を 考えられるということです。 つまり、何らかの方法で比較以外の Sorting プログラムを考案した時、ここ で示した結果とは何ら関連せずに高速なアルゴリズムになる可能性があります。

では、最低限比較の数を考えます。 一回の比較では大小関係が一つだけ求まります。 これでプログラムの流れは 2 つに分かれます。 さて、ここでプログラムの流れを図に表すことを考えます。 「データの i 番目と j 番目を比較する」という ような比較をノードにすると、プログラムの流れは二分木になります(計算の 流れを木で表したものを 計算木と呼びます)。 計算木は入力の可能性すべてを表しますので、配列の内容は未知でも配列 の数が決まっていれば、プログラムの流れの分岐の仕方を全て記した計算木は 一意に定まります。 ところで、プログラムに与える入力は、データの数を n で表すと、 n! 通りあります。 プログラムの終端は計算木の葉になりますので、もし計算木の葉の数が n! より少ないと、異なるデータの並びに対して、同じ並べ替えの 順序で出力することになります。 従って、計算木の葉 の数は少なくとも n! 以上なければならないことになります。 従って、計算木は二分木なので、木の深さは少なくとも log n! は必要になります。 一回のソーティングに必要な比較回数は、この計算木の深さに対応するので、 ソーティングの比較回数は Ω( log n! ) となります。 ここで次の Stirling の公式を使います。

n ! sim sqrt{2 pi} roman {e}^{-n} n^{n + (1/2)}

これにより、ソーティングに必要な比較回数は Ω( n log n ) になります。

7-4. 宿題

7-5. 次週の予告

次回は非決定性 Turing 機械についてお話します。

坂本直志 <[email protected]>
東京電機大学工学部情報通信工学科