ソートアルゴリズムが最善でO(nlog(n))になる話（笑）メモ

こんばんは。

アルゴリズムの勉強していたら、ソートアルゴリズムは数学的に最善でO(nlog(n))になるとかなんとか書いてありました。ふーん。とは言えなんでそうなるんでしょう。

アルゴリズムクイックリファレンス

この本に書いてあった証明は数式以外はとてもわかり易かったんですが、それ以降の数式がわけわからなかったのでちょっと書いておきます。どこまで正確なのかわからないので正直不安なんであんまり当てにしないでください。

そもそもソートするデータが全部でn個あった時（配列なら長さがnってことですね）、n個のデータを1つずつ取って並べるのと一緒なので、データの並び方をすべて数えるとnの階乗（n!）になります。
この時、ソートするアルゴリズムは、2つの要素を比べて整列するものです。これはわかりますよね。ここまではすごくよく分かる。簡単。

この時、二分木を考えます。はぁ？と思うでしょうが、ひとまずスルーしてください。この二分木、葉がそれぞれ順列の一つと対応しています。葉の数は当然ですがn!です。
二分木の分岐（接点）はそれぞれ、データの1番目≦2番目、1番目≦3番目、という、それぞれの要素と比較する条件式になっています。要するに、その条件式が正しいか正しくないかでどの葉に向かうかが決まるわけです。言葉だとすっごいわかりづらいですが、葉1つが順列1つになっていて、それをどういう風に葉に当てはめていくかを考えていくと、なんとなく理解しやすいと思います。

さて、順列の全通りが二分木の葉になったわけです。この二分木、どんなカタチになっているかは分かりませんが、必ず高さが最小になる葉が存在しているはずです。この最小の高さをhと置きます。二分木の接点は条件式でしたから、hは根から最小の葉までの比較回数になっている、とも見れるわけです。

この時、最善のオーダーを考えたいのですから、二分木の形がわからないと不都合が出てきます。ここで一度、二分木を完全二分木であると仮定します。完全二分木とは、最後の要素以外（一番下の葉の部分以外ってことです）、左右両方の子を持っている場合の二分木のことです。

完全二分木は全部で2^h-1個の接点があります。しれっと言ってますが、高さhが1増えると2の階乗分だけ接点が増えるのは二分木なんですから当たり前ですし、-1があるのは根の部分はどう頑張っても一つしか接点が存在しないのですから、当然といえば当然。
そして、この完全二分木の高さはlog(n+1)になります。当然logの底は2です。＋1ついてるのは根の接点のことです。さっき引いたやつですね。

ここでさっきの完全二分木であるという仮定をなかったことにします。要するに不完全な木になってしまうということですね。完全二分木の時に高さhはlog(n+1)だったわけですが、当然ながら不完全な木になってしまったのでこのままlog(n+1)であるということはできないわけです。ということは、

h ≧ ceiling(log(n+1))

となります。このceilingというのは要するに引数を引数よりも小さくない最小整数にして返す関数です。ざっくり言うと切上げです。詳細はこちらの天井関数を参照してください。

ここでようやく一番最初に考えた、順列の並べ方はn!である、を使います。n!だけ葉が存在する二分木の高さが求められれば、それがソートアルゴリズムの限界になるわけです。なんか厨ニっぽいですね。

n!だけ葉が存在する二分木全体の接点の数は少なくともn!個です。要素と要素の比較は葉に近づくにしたがって重複しなければいけませんから、その都度増えていくことを考えると、自ずとn!になることがイメージできると思います。

さて、最善の場合の接点の数は求まりましたから、あとはこれの対数をとれば高さが求まります。つまり今から

h = log(n!)

を計算します。ぱっと見どうすりゃいいんだって感じがしますが、ここでスターリングの公式による近似をします。これ、私も今回はじめて知ったんですが、わかってしまえばどうということはありません。

log(a*b)=log(a)+log(b)なのはご存知のとおりだと思いますが、これをn!にも考えてみると、式はこんなかんじに変形できます。

h = log(n) + log(n-1) + ... + log(2) + log(1)

つまり、1~nまでの対数の和になるわけです。ここまで来たら後は積分するだけです。

h = {1 ~ n} log(x)dx

記号出せなかったので勘弁して下さい。でもなんとなくわかるでしょう。察してください。あとはこれを部分積分して計算するだけです。計算の詳細はここでは省略しますが、このページの中程あたりに詳しく記載されているので興味がある方は見てみてください。

スターリングの公式

h = nlogn - n + 1

ここでようやくnlognが出てきました。後はこれのオーダーを取ってO(nlogn)として終了です。オーダー記法に則れば、-n+1は無視できます。そうだったはずだよな。うん。

というわけで、文章だらけですが、とりあえずソートアルゴリズムがどうやって最善でnlognであると求めるかを書いてみました。ぶっちゃけ半分以上本から持ってきているんですが、それでもわかりやすく書きなおしたつもり。まぁ間違えてたらどうしようもないんだけど。

多分どこかしかおかしい所あると思うので、コメントでの指摘等していただければありがたいです。