💨

Lower bound for comparison-based sorting

2021/04/13に公開

比較によるソーティングの「計算量の下界」の話である。

比較じゃないソーティングはあるのか？ => ある。distribution sortingなどで検索してみよう。

さて今回は、比較を使うソーティングアルゴリズムについてだ。

ソーティングアルゴリズムの計算量の下界というのは、worst case(アルゴリズムの計算時間が最悪の場合)においてn個の要素を並び替えるのに要する、要素同士の比較の回数のことを指す。

計算時間とかいてしまうと、実行環境や言語に依存してしまうので、要素同士の比較の回数のことを計算量と便宜的に呼ぶようになっている。

計算量の評価には「漸近記法」を用いる。

計算量の下界ではビッグオメガ Ωを記号として用いる。

アルゴリズムAは、Ω（n)の計算量である、と書かれていたら、n個の要素を並び替えるのに、最悪の場合n回比較が必要なんだなぁと考えよう。

そして、タイトルとなっているLower bound for comparison-based sortingについては、以下の命題が真である。

「いかなるcomparison-based sortingにおいてもn個のオブジェクトを昇順/降順に並び替える場合のworst caseの計算量は $Ω(n \log_2 n)$ となる」

どうしてそうなるかを書いていくが、「計算量の下界」などど言われても小難しいので3個の要素の並び替えを例としてまず見ていく。

a,b,cを並び替える

a,b,cという数値があるとする。これを昇順に並び変える場合、何回要素の比較が必要だろうか。

[比較１] a,bの大小を比べる。aよりbの方が大きいとする。
[比較2] b,cの大小を比べる。bよりcの方が大きいとする。

a<b<cという順番だとわかるので、比較は2回で終わる。
aよりbが小さい場合など網羅的に場合わけをすると以下のような2分木の木構造のモデルを書くことができる。

まずaとbの比較が木の根となっている。葉に相当するものとして、比較後の結果を書いている。比較後の結果はもちろん、a,b,cのpermutationとなっている。

葉は6枚あり、少なくとも3!個(=要素のpermutation数)となっている。
比較回数が最悪となるのは、並び替えの結果がa,c,bかc,a,bかb,c,aかc,b,aとなっている場合で、木構造の深さが少なくとも3となるとき。

葉の枚数l, 木構造の深さd、n個の要素での比較へと一般化すると

葉の枚数はl枚は最低でもn!枚ということは

l \ge n!

葉の枚数に関しては、深さdの時の葉の枚数　 $2^{d}$ 　が最大となることから、以下が成り立つ。

2^d \ge l

これは以下の式と等価である。

d \ge \log_2 l

「いかなるcomparison-based sortingにおいてもn個のオブジェクトを昇順/降順に並び替える場合のworst caseの計算量は $Ω(n \log_2 n)$ となる」

さて、いまは上のlemmaを確認したいわけであるが、これは、比較を使ったソーティングでn個の要素を並び替える場合、比較回数は最低でも、 $Ω(n \log_2 n)$ となるということだ。

比較回数は、a,b,cの3つ要素で見た場合でわかるように、木構造の深さdである時が最低（=一番多い）である。このdの値についてorder preserving lower estimationを試みる。まずはこれまで出してきた式からdについて以下のことが言える。

d \ge \log_2 l \ge log_2 n!

これより、以下について、order preserving lower estimationを行えばいいことがわかる。

log_2 n!

それではおこなう。

\log_2 n! {\displaystyle =\,} \log_2(1 \cdot 2 \cdot \dots n)

{\displaystyle =\,} \log_2 1 + \log_2 2 + \cdot \log_2 n

\ge \log_2 \frac{n}{2} + \cdot + \log_2 n

\ge \frac{n}{2} \log_2 \frac{n}{2}

{\displaystyle =\,} Ω ( n \log_2 n)

3行目の不等号は、2行目のn個ある項のうち、 $\log_2 \frac{n}{2}$ 以降の $\frac{n}{2}$ 個の項のみを取り出し評価した。

そこから、 $\frac{n}{2}$ 個について以下が成立する。

\log_2 \frac{n}{2} \ge \log_2 \frac{n}{2}

\log_2 (\frac{n}{2} + 1) \ge \log_2 \frac{n}{2}

\log_2 (\frac{n}{2} + 2) \ge \log_2 \frac{n}{2}

\cdot

\log_2 n \ge \log_2 \frac{n}{2}

このように、4行目の不等号の評価が可能であった。

もう一度駆け足で見てみよう。

n個のオブジェクトを並び替えることを想定し、葉の枚数l、木の深さdとしてみよう。