(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! = 6 通りあるからである。
(40.2) 同様の議論により、 高々 k 回の比較で N 個の元をソートするプログラムがあったとすると、 2k ≧ N! が成り立つ。 自然対数をとると 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)) のソートアルゴリズムを学ぶ。 オーダーの点から見れば、これよりも効率のよいアルゴリズムは存在しない。 あとは、係数をどれだけ小さくできるか、である。
今回で、この授業のうち、ソートの部分の半分が終わります。 授業の進め方などについて感想のある方は、 私が回っていったときに語りかけるか、 メールで送ってください。
また、時間外に、話しにきてくださることも歓迎します。 数学の質問も、です。