第 7 回下限

本日の内容

7-1. 宿題の解答
7-2. 計算量の下限
7-3. Sorting
7-4. Sorting の比較の数
7-5. 宿題
7-6. 次週の予告

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

7-1. 宿題の解答

$g (n) \neq O (f (n))$
$f (n) \neq o (g (n))$

この両方が成り立つ $f (n), g (n)$ を見つける。まず、これを論理式で表すとつぎのようになる。

$⫬ (\exists c > 0) (\exists N_{0}) (\forall n \geq N_{0}) [g (n) \leq c f (n)]$
$= (\forall c > 0) (\forall N_{0}) (\exists n \geq N_{0}) [g (n) > c f (n)]$
$= (\forall c > 0) (\forall N_{0}) (\exists n \geq N_{0}) [f (n) < c g (n)]$
$⫬ (\forall c > 0) (\exists N_{0}) (\forall n \geq N_{0}) [f (n) \leq c g (n)]$
$= (\exists c > 0) (\forall N_{0}) (\exists n \geq N_{0}) [f (n) > c g (n)]$

これより、 g は f を無限回上回るも、無限回下回らなければならない。ここで、 g は f よりオーダの大きな関数と小さな関数を行き来すると仮定するとうまくいく。つまり、 f(n)=n^2 としたとき、 g(n) は n と n^3 のあいだを行き来する関数と定義する。

つまり、 g(n) は g(1)=1 とし、 g(2)=2^3 とする。そして、 g(2^3-1) までは 2^3 としておき、 g(2^3)= (2^3)^3 = 2^(3^2) とする。そして、 g(2^(3^2)-1)までは 2^(3^2) とする。つまり、 g(n) は 2^(3^k)≤ n < 2^(3^(k+1))-1 の時、2^(3^(k+1)) とする。

7-2. 計算量の下限

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

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

「ある数 $c > 0$ と $N_{0}$ が存在し、全ての $N_{0}$ より大きい数 $n$ に対して $f (n) \geq c g (n)$ が成り立つ」。なお、これは一階述語論理式では次のように書けます。

(\exists c > 0 N_{0}) (\forall n \geq N_{0}) [f (n) \geq c g (n)])

7-3. Sorting

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

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

クイックソート

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

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

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

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

O (n) + 2 O (\frac{n}{2}) + 4 O (\frac{n}{4}) + ... + n O (1)

= \sum_{i = 1}^{log n} 2^{i} O (\frac{n}{2^{i}})

= O (n log n)

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

O (n) + (1 + O (n - 1)) + (1 + O (n - 2)) + ... + (1 + O (1))

= \sum_{i = 1}^{n - 1} (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-4. Sorting の比較の数

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

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

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

n! \sim \sqrt{2 π} e^{- n} n^{n + \frac{1}{2}}

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

7-5. 宿題

1

Sorting の計算量の下限が $Ω (n log n)$ と言い切れない理由は何か?

2

2×2 の行列の積は高々 8 回でできるが、これは実は掛け算の回数を 7 回にすることができる。その方法を考えよ。

7-6. 次週の予告

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

坂本直志 <sakamoto@c.dendai.ac.jp>
東京電機大学工学部情報通信工学科

第 7 回 下限