期待計算量・オーダー n log2(n)
数あるソートアルゴリズムのうち、高速で安定しているとされるクイックソートやマージソートでは、期待計算量が O[n log(n)]となります。単純ソートでは、計算量がO[n2]、比較的単純な指数関数あったのに対し、計算量にlog（自然対数）が入ってきます。これはなぜでしょうか？
この記事から数記事を書けて、この”log“がなぜ出てくるのかを、まずは、簡単に概要をイラストをもとに理解し、その後、アルゴリズムから計算量を求めて数学的に理解。最終的にはもっと踏み込んでlogが出てくる理由について深く理解していこうと思います。
ちょっと踏み込んだ次の記事はこちら
なぜ計算量がn log(n)？分割統治法の計算量を数学的に導く【ソートアルゴリズム入門】#8
高速なアルゴリズムに出てくる「n log n」。この計算量を「漸化式（ぜんかしき）」という数学の手法で証明します。「log(n)はどこから来たの？」という疑問を、式を展開しながら中学生にも分かるように解き明かします。
計算量って何？という方は、以下の記事で紹介しています。
計算量 とは？データ数が倍になると手間が4倍？単純ソートの計算量O[n^2]を中学生でもわかるように解説【ソートアルゴリズム入門】#4
なぜ単純ソートはデータが増えると遅くなる？その「遅さ」を測るモノサシが「計算量」と「O記法」です。この記事では、O(n^2) といった計算量の考え方を、中学生でもわかる「作業の手間」に例えて解説。グラフで「増え方の勢い」を学び、次の高速なアルゴリズムへ進みましょう。
ソートアルゴリズムに「log(n)」がなぜ出てくるのか分かる。
視覚的に「log(n)」の正体を探る
log(n)（ログ・エヌ）という言葉に、数学アレルギーを感じる必要はまったくありません。ここでは微分したり式を解かなくてもわかるようイラストや例を用いて紹介します。
log(n)は、ざっくりと言えば「問題（データ）を「半分」に何回分割できるか？」という回数を示す「最強の効率の良さ」の象徴ともいえるものです。この分割してソートする方法を”分割統治法“といいます。
辞書で”ソート”を調べてみる例
この分割について、一番わかりやすいのが「辞書で単語を探す（二分探索）」例です。
Q.1000ページの辞書で「ソート」という単語を探すとき、あなたはどうしますか？
ただし、50音順に単語が並んでいるが見出しがないちょっと不便な辞書であるとします。また、頭文字ごとの単語数も不定です。(例えば、もし、頭文字当たりの単語数がある程度同じなら、初めから50分割して開くなどの方が効率的になりますが、それができないとします。) (見出しを用いるようなアルゴリズムもありますがここでは取り上げません)
- 一番初めのページから、順番に”ソート”が出てくるか全部確認する？
- ソートは”ソ”から始まるので、まずソがどの辺にあるか探す？
上の二つの方法を計算量の考えかたを使ってオーダーを考えてみます。
オーダーがよくわからない！という方はこちらの記事で詳しく紹介しています。
計算量 とは？データ数が倍になると手間が4倍？単純ソートの計算量O[n^2]を中学生でもわかるように解説【ソートアルゴリズム入門】#4
なぜ単純ソートはデータが増えると遅くなる？その「遅さ」を測るモノサシが「計算量」と「O記法」です。この記事では、O(n^2) といった計算量の考え方を、中学生でもわかる「作業の手間」に例えて解説。グラフで「増え方の勢い」を学び、次の高速なアルゴリズムへ進みましょう。
二つの方法の”項目をチェックする手間”(計算量)を考えると以下のようになります。
- O(n) の戦略 (非効率): 1ページ目から順に探す。最悪全項目数分、回数がかかる。(例：”ん”から始まる単語だったら最後まで出てこない…)
- O(log n) の戦略 (超効率):
- まず真ん中（500ページ目）を開く。開いたら”タ”の項目でした。”ソ”は”タ”より前です。
- これで一瞬にして後半の500ページを捨てることができた。
- 残った500ページ（1～500）のとりあえず、真ん中（250ページ目）を開く。すると”オ”の項目でした。”ソ”は”オ”より後です。
- これで前半の250ページを捨てた。
- 残りは250ページ。また半分に…。
もし、１つ目の方法で辞書を引こうとしたら、１単語を引くのに、数時間かかってしまいます。しかし、分割する方法を使ったら、1回の処理で問題（探す範囲）が「半分」になるので、データが100万件あっても約20回、10億件あっても約30回で答えにたどり着くことができます。
図にしたらどんな感じ？
方法１だと、１項目ずつもう探索しなくていい部分が確定していきますが、方法２なら、一気にその時の残り半分を探索しなくていい部分とすることができているのがわかります。
これを数式で表したら？
辞書の例では、全ページ数を1000としましたが、全ページ数を１から順に増やしていったとしたとき、目的のページを開くまでのステップ数をグラフにしました。また、比較のためlog2(全ページ数)のグラフも並べてみました。
図 logと二分探索のステップ数グラフ
図を見れば、必要なステップ数とlogが大体一致していることが確認できると思います。ステップ数は、ページ数が倍にならないと増えないので階段状にlogのグラフとずれているようにも見えますが、もっとデータ数が増えてくると、ほどんどlogのグラフと一致します。
まとめ
データをうまく「半分にできる回数」こそが、log(n) に表れていることが理解できたでしょうか。
記事のはじめで取り上げたクイックソートやマージソートは”分割統治法“を用いており、うまくデータを分けて、高効率にソートを行っています。そのため、この半分にするときの”手間”を表すlog(n)が、計算量に姿を現すのです。
“分割統治法“を用いたソート
マージソートの仕組みを徹底解説！アニメーションで学ぶ「分割統治」ソート・併合ソート【ソートアルゴリズム入門】#6
「マージソート」は「分割統治法」に基づく高速なソートです。O(N^2)の単純ソートとは異なり、O(N log N)の計算量を実現します。データを半分に「分割」し、ソートしながら賢く「結合（マージ）」する仕組みを図解します。
次回の記事では、もうちょっと数学的に計算量を評価してみようと思います。(11/27投稿予定)
なぜ計算量がn log(n)？分割統治法の計算量を数学的に導く【ソートアルゴリズム入門】#8
高速なアルゴリズムに出てくる「n log n」。この計算量を「漸化式（ぜんかしき）」という数学の手法で証明します。「log(n)はどこから来たの？」という疑問を、式を展開しながら中学生にも分かるように解き明かします。
ここまで読んでいただきありがとうございます。
では、次の記事で。 lumenHero
