2009 年度「計算数学」 2009-11-27

§40 ソートプログラムの効率の限界

(40.1) 互いに異なる三つの数 a, b, c を比較して小さい順に並べるとしよう。 下の図は、最初に a < b かどうかを調べ、「はい」なら上へ、 「いいえ」なら下へ進む、と読む。一番右に書かれているのが、得られた結論である。

                          +-               「a < b < c」
                          |
            +- (b < c ?) -+
            |             |             +- 「a < c < b」
            |             +- (a < c ?) -+
            |                           +- 「c < a < b」
-(a < b ?) -+
            |                           +- 「b < a < c」
            |             +- (a < c ?) -+
            |             |             +- 「b < c < a」
            +- (b < c ?) -+
                          |
                          +-               「c < b < a」
高々3回の比較で結論に至るが、これを2回に減らすことは不可能である。 それは、2回の分岐では4通りの結論しかありえないのに対し、 結論は 3! = 6 通りあるからである。

(40.2) 同様の議論により、 高々 k 回の比較で N 個の元をソートするプログラムがあったとすると、 2kN! が成り立つ。 自然対数をとると k log(2) ≧ log(N!) = log(1) + log(2) + log(3) + ... + log(N-1) + log(N) となる。 この右辺は、関数 y = log(x) の積分と比較することにより、 N log(N) - N + 1 よりも大きく、 (N+1) log(N+1) - N よりも小さいことがわかる。 N が十分大きければほぼ N log(N) とみなせる。 よって、 N が十分大きいとき、 “ほぼ k ≧ N log(N) / log(2)”である。 公式 logac = logab ・logbc, あるいは logac / logab = logbc を思い出すと、 これは“ほぼ k ≧ N log2(N)”となる。 情報科学では対数の底として 2 を選ぶことが多いらしい。 その約束を採用するなら、“ほぼ k ≧ N log(N)”と書ける。 オーダーで言えば、Ο(N log(N)) が限界となる。 これより真に小さいオーダーの計算量で済むアルゴリズムは存在しない。

(40.3) (ただし、これは、 二つの要素の比較と互換を基礎としてアルゴリズムを構成する限り、 の話である。 それ以外の、ソートに都合のよい機能を持ったコンピュータがでてきて、 基礎になる演算が比較・互換以外のものになれば、 その回数は上の限界よりも少ないことがあり得る。)

(40.4) 次回から、Ο(N log(N)) のソートアルゴリズムを学ぶ。 オーダーの点から見れば、これよりも効率のよいアルゴリズムは存在しない。 あとは、係数をどれだけ小さくできるか、である。

今回で、この授業のうち、ソートの部分の半分が終わります。 授業の進め方などについて感想のある方は、 私が回っていったときに語りかけるか、 メールで送ってください。

また、時間外に、話しにきてくださることも歓迎します。 数学の質問も、です。


岩瀬順一