分割統治法の計算量 O [ n log(n) ]
前回の記事では、マージソートのような高速なアルゴリズムが \(O[n log n]\) となる理由を、「分割の深さ（高さ）」×「各層での作業量」という視覚的なイメージで捉えました。
- レベル（深さ）: データを半分に分割していく回数 = 約 \( log (n) \) 回
- 作業量（幅）: 各レベルで、結局 n 個のデータすべてをマージ（結合）する = 約 n 回
したがって、全体の作業量は 約 \(log (n)\) 回 × 約 n 回 (分割の作業×結合の手順)になる、という概要でした。
なぜ計算量がn log(n)？”log”が出てくる訳をわかりやすく紹介【ソートアルゴリズム入門】#7
O[n^2] を超える高速なソート（クイックソート等）は O[n log n] と呼ばれます。なぜ突然log（対数）が出てくるのか？ その秘密は「半分に分ける」という最強の戦略「分割統治法」にありました。log の正体を視覚的に解き明かします。
今回は、この視覚的なイメージが本当に数学的に正しいのかを、「漸化式（ぜんかしき）」という手法を使って証明していきます。
ここからは少し難易度が上がりますが、コンピュータサイエンスの非常に重要な考え方です。
アルゴリズムの「コスト」を数式で表す
まず、アルゴリズムの処理の手間（コスト）を数学の関数で定義します。
「データ数 \(n\) のリストをソートするためにかかる総コスト」を \(T[n]\) と置くことにします。
\[T[n] = n個のデータにかかるコスト\]
この \(T[n]\) を、マージソート（分割統治法）の手順に沿って分解してみましょう。
- 1. 分割 (Divide):\(n\) 個のデータを \(n/2\) 個の2つのリストに分割します。これは一瞬（または \(O[1] \)で終わります。）
- 2. 統治 (Conquer):分割した2つの \(n/2 \) 個のリストを、再帰的に（自分自身を呼び出して）ソートします。最後まで分割したとき完了となるので、\(n/2 \) 個にかかるコストは \(T[n/2] \) です。それが2つあるので、合計コストは \(2 \times T[n/2] \) となります。
- 3. 結合 (Combine):ソート済みの2つの \(n/2 \) のリストを、1つの \(n \) のリストにマージ（結合）します。前回の記事で見たように、このマージ作業は「両方のリストの先頭を見比べて、小さい方を新しいリストに入れる」を繰り返すため、結局 (最悪の場合は、) \(n \) 個すべての要素を1回ずつ触る必要があります。したがって、ここのコストは \(O[n] \) （または単純に \([cn]\) と書けます ※\(c\)は定数で一度の結合のコスト）です。
これら1〜3を合計したものが、 \(T[n]\) となるはずです。
漸化式を立てる
上記の分析を1つの数式にまとめます。
分割統治法の漸化式
ある定数 \(c\) を使って「分割コスト」と「結合コスト」の合計を \(cn\) と表現すると（ \( O(1) + O[n] \) は \(O[n]\) に吸収される※オーダーの考え方）、マージソートの総コスト \(T[n]\) は、以下の漸化式（ぜんかしき）で表すことができます。
\[ T[n] = 2T[n/2] + cn \]
この式は、アルゴリズムの構造そのものを表しています。
「\(n\) 個のソート(\(T[n] \))」は、「\(n/2\) 個のソート(\(T[n/2]\))」2回分と、「\(n\) 個のマージ(\(cn\))」1回分でできている、という意味です。
O（オーダー）記法の考え方
この「手間の増え方の勢い」を、世界共通のシンプルな記号で表すルールが「O（オーダー）記法」です。(この”O”をランダウの記号と言います。)
オーダーのルール(超簡単に言うと?)
- 定数（係数）は無視する
- 「一番勢いが強いヤツ」だけを残す
計算量 とは？データ数が倍になると手間が4倍？単純ソートの計算量O[n^2]を中学生でもわかるように解説【ソートアルゴリズム入門】#4
なぜ単純ソートはデータが増えると遅くなる？その「遅さ」を測るモノサシが「計算量」と「O記法」です。この記事では、O(n^2) といった計算量の考え方を、中学生でもわかる「作業の手間」に例えて解説。グラフで「増え方の勢い」を学び、次の高速なアルゴリズムへ進みましょう。
漸化式の初項
また、この再帰的な計算が止まる”ベースケース”(初項の値)も必要です。
データが1個 (\(n=1\)) の場合、ソートは不要（コストは一定）です。これを定数 (c’)（シーダッシュ）で表すことにします。
\[ T[1] = c’ \]
これで、計算の準備が整いました。
漸化式を「展開」して解く
この \( T[n] = 2T[n/2] + cn \) という式を、ドミノ倒しのように展開していきます。
まず、\(T[n]\) の式はこうでした。
\( T[n] = 2T[n/2] + cn \)
では、式の右辺にある \(T[n/2]\) は何でしょうか？
漸化式の \(n\) に \(n/2\) を代入すればわかります。
\( T[n/2] = 2T[(n/2)/2] + c(n/2) = 2T[n/4] + cn/2 \)
これを、元の \(T[n]\) の式に代入（展開）してみます。
\( T[n] = 2 \times ( 2T[n/4] + cn/2 ) + cn \)
\( T[n] = 4T[n/4] + cn + cn \)
\( T[n] = 4T[n/4] + 2cn \)
パターンが見えるまで、もう一度だけ展開してみましょう。
\(T[n/4]\) は、\(n\) に \(n/4\) を代入して、
\( T[n/4] = 2T[(n/4)/2] + c(n/4) = 2T[n/8] + cn/4 \)
これを \(T[n] = 4T[n/4] + 2cn\) に代入します。
\( T[n] = 4 \times ( 2T[n/8] + cn/4 ) + 2cn \)
\( T[n] = 8T[n/8] + cn + 2cn \)
\( T[n] = 8T[n/8] + 3cn \)
パターンの発見と一般化
ここで、展開した式を並べてみます。
- 1回目: \( T[n] = 2^1 T[n/2^1] + 1cn \)
- 2回目: \( T[n] = 2^2 T[n/2^2] + 2cn \)
- 3回目: \( T[n] = 2^3 T[n/2^3] + 3cn \)
このパターンから、\(k\) 回展開したときの一般式は、以下のように推測できます。
\( T[n] = 2^k T[n/2^k] + kcn \)
この \(k\) は、前回の記事で見た「分割の深さ（レベル）」に他なりません。
なぜ計算量がn log(n)？”log”が出てくる訳をわかりやすく紹介【ソートアルゴリズム入門】#7
O[n^2] を超える高速なソート（クイックソート等）は O[n log n] と呼ばれます。なぜ突然log（対数）が出てくるのか？ その秘密は「半分に分ける」という最強の戦略「分割統治法」にありました。log の正体を視覚的に解き明かします。
計算の終了（ベースケースへの到達）
この展開は、いつ止まるのでしょうか？
それは、\(T[…]\) の中身がベースケースである \(T[1]\) になった時です。
つまり、\( n/2^k = 1 \) となった時に止まります。
この式を変形すると、 \( n = 2^k \) となります。
両辺の対数（底は2）をとると、
\( k = \log_2 n \)
ついに、前回の記事で視覚的に捉えた \( \log n \) が、数式の上でも「展開が止まるまでの回数（＝深さ）」として導かれました。
結論：\(O[n \log n]\) の導出
あとは、この \(k = \log_2 n\) を、先ほどの一般式 \( T[n] = 2^k T[n/2^k] + kcn \) に代入して、計算を完了させるだけです。
\( T[n] = 2^{\log_2 n} \times T[n / 2^{\log_2 n}] + (\log_2 n) \times cn \)
ここで、対数の重要な性質を使います。
- \( 2^{\log_2 n} = n \) です。（例: \( 2^{\log_2 8} = 2^3 = 8 \)）
- \( T[n / 2^{\log_2 n}] = T[n / n] = T[1] \) です。
- \( T[1] \) は、ベースケースの定数 \(c’\) です。
これらを代入すると、
\( T[n] = n \times T[1] + cn \log_2 n \)
\( T[n] = c’n + cn \log_2 n \)
これで、\(T[n]\) を \(n\) の式だけで表すことができました。
この \(c’n + cn \log_2 n\) という結果を、アルゴリズムの計算量を表す \(O\) 記法で評価します。
\(n\) が非常に大きくなった時、\(n\) の項と \(n \log n\) の項では、どちらがより支配的（増加が速い）でしょうか？
答えは \(n \log n\) です。(\(定数\times n\) と \(nに対して単純増加する log n \times n\)の比較なので)
したがって、マージソートの計算量は、
\[ O[n \log n] \]
であると、数学的に証明することができました。
（※\(O\)記法では対数の底は無視するため、\(\log_2 n\) は \(\log n\) と表記します）
まとめ
前回の記事の「深さ(\( \log n \)) × 幅(\( n \))」という視覚的なイメージが、漸化式を解くことで数学的にも「\(O[n \log n]\)」として裏付けられました。
この \(O[n \log n]\) という計算量は、比較を元にしたソートアルゴリズムにおいて理論上の最速（平均計算量）とされています。
#6で紹介したマージソートは、どのようなデータ配列に対しても安定してこの \(O[n \log n]\) の性能を発揮する、非常に優秀なアルゴリズムです。
しかし、マージ（結合）のために一時的にデータをコピーする「余分なメモリ領域」が必要になるという欠点もあります。
次回は、同じ「分割統治法」を使いながらも、このメモリの問題を解決し、多くの場面で（平均的に）マージソートより高速に動作する「クイックソート」について解説します。
クイックソート
クイックソートの仕組みを徹底解説！アニメーションで学ぶ「圧倒的平均最速」ソート【ソートアルゴリズム入門】#9
分割統治法を使ったソートの王道”クイックソート” 以前の記事で、分割統治法を用いたアルゴリズムとして、常に安定した \(O(n \log n \) の性能を誇る「マージソート」を紹介しました。 マージソートは「分割は単純 […]
マージソート
マージソートの仕組みを徹底解説！アニメーションで学ぶ「分割統治」ソート・併合ソート【ソートアルゴリズム入門】#6
「マージソート」は「分割統治法」に基づく高速なソートです。O(N^2)の単純ソートとは異なり、O(N log N)の計算量を実現します。データを半分に「分割」し、ソートしながら賢く「結合（マージ）」する仕組みを図解します。
ここまで読んでいただきありがとうございます。
では、次の記事で。 lumenHero
