O(n log n)とは？線形対数計算量をわかりやすく解説【アルゴリズム入門】
プログラミングやアルゴリズムを学ぶ上で避けて通れないのが「計算量」の概念です。中でも**O(n log n)**という線形対数計算量は、実用的なアルゴリズムで頻繁に登場します。
本記事では、O(n log n)の意味、具体例、そしてなぜこの計算量が重要なのかを初心者にもわかりやすく解説します。
テックジム東京本校では、情報科目の受験対策指導もご用意しております。
目次
O(n log n)とは？基本概念
計算量の表記法
O(n log n)は「オーダー・エヌ・ログ・エヌ」と読み、アルゴリズムの時間計算量を表すビッグオー記法の一つです。
- n: データの要素数
- log n: nの対数（通常は底が2の対数）
- n log n: nとlog nの積
どのくらいの速さ？
計算量を遅い順に並べると以下のようになります：
O(n²) > O(n log n) > O(n) > O(log n) > O(1)
遅い ←―――――――――――――――――――→ 速い
O(n log n)は、O(n)（線形時間）よりは遅いものの、O(n²)（二乗時間）よりは圧倒的に速い計算量です。
具体的な数値で理解する
データ数nに対する操作回数の目安：
| データ数 (n) | O(n) | O(n log n) | O(n²) |
|---|---|---|---|
| 10 | 10 | 約33 | 100 |
| 100 | 100 | 約664 | 10,000 |
| 1,000 | 1,000 | 約9,966 | 1,000,000 |
| 10,000 | 10,000 | 約132,877 | 100,000,000 |
データが大きくなるほど、O(n log n)とO(n²)の差は顕著になります。
O(n log n)の代表的なアルゴリズム
1. マージソート（Merge Sort）
最も有名なO(n log n)のソートアルゴリズムです。
動作原理：
- データを半分に分割し続ける（log n回）
- 分割したデータをマージしながらソート（各レベルでO(n)）
- 分割とマージを組み合わせてO(n log n)を実現
def merge_sort(arr):
if len(arr) <= 1:
return arr
# 分割（Divide）
mid = len(arr) // 2
left = merge_sort(arr[:mid])
right = merge_sort(arr[mid:])
# マージ（Conquer）
return merge(left, right)
def merge(left, right):
result = []
i = j = 0
while i < len(left) and j < len(right):
if left[i] <= right[j]:
result.append(left[i])
i += 1
else:
result.append(right[j])
j += 1
result.extend(left[i:])
result.extend(right[j:])
return result
2. クイックソート（Quick Sort）
平均的にO(n log n)、最悪の場合O(n²)となるソートアルゴリズムです。
特徴：
- 実用上は非常に高速
- ピボット選択により性能が変わる
- 多くのプログラミング言語の標準ソート関数で採用
3. ヒープソート（Heap Sort）
常にO(n log n)を保証するソートアルゴリズムです。
特徴：
- ヒープデータ構造を利用
- 追加のメモリをほとんど必要としない
- 最悪ケースでもO(n log n)を保証
4. その他の応用例
- FFT（高速フーリエ変換）: 信号処理で使用
- 平衡二分探索木の構築: AVL木、赤黒木など
- 座標圧縮: 競技プログラミングでよく使用
なぜO(n log n)が重要なのか
1. 比較ソートの理論的限界
重要な定理: 比較ベースのソートアルゴリズムでは、O(n log n)が最良の計算量となります。
これは数学的に証明されており、比較のみでソートする場合、これ以上速くすることはできません。
2. 実用性の高さ
大規模データの処理において、O(n log n)は実用的な速度を提供します：
- 100万件のデータをソート: 約2000万回の操作
- O(n²)の場合: 1兆回の操作（500,000倍遅い！）
3. 分割統治法の代表例
O(n log n)のアルゴリズムの多くは「分割統治法」というアルゴリズム設計手法を採用しており、この手法を学ぶ良い教材となります。
O(n log n)を理解するための視覚的イメージ
木構造で考える
O(n log n)は「木構造」でイメージすると理解しやすくなります。
[8要素] ← レベル0: 1つのノード
/ \
[4要素] [4要素] ← レベル1: 2つのノード
/ \ / \
[2] [2] [2] [2] ← レベル2: 4つのノード
/ \ / \ / \ / \
[1][1][1][1][1][1][1][1] ← レベル3: 8つのノード
- 木の高さ: log n（8要素なら3レベル）
- 各レベルの処理: O(n)（全要素を処理）
- 合計: O(n) × log n = O(n log n)
パフォーマンス比較：実測例
以下は、異なる計算量のアルゴリズムの実行時間の目安です：
データ数: 10,000件の場合
- O(n): 約0.001秒
- O(n log n): 約0.013秒
- O(n²): 約10秒
- O(2ⁿ): 実行不可能
大規模データでは、O(n log n)とO(n²)の差は圧倒的です。
よくある質問（FAQ）
Q1: log nの底は何ですか？
計算量理論では、底が2でも10でもeでも、底の変換は定数倍にしかならないため、ビッグオー記法では底を省略します。通常は底2と考えて問題ありません。
Q2: O(n log n)より速いソートアルゴリズムはありますか？
比較ベースのソートではO(n log n)が最速ですが、特定の条件下では以下のアルゴリズムがO(n)で動作します：
- カウンティングソート: 整数で値の範囲が小さい場合
- 基数ソート: 固定長の文字列や整数
- バケットソート: データが均等に分布している場合
Q3: クイックソートとマージソートはどちらが速いですか？
平均的にはクイックソートの方が速いことが多いですが、最悪ケースではマージソートの方が安定しています。用途に応じて使い分けることが重要です。
Q4: 再帰処理のスタックメモリも考慮すべきですか？
はい。マージソートの空間計算量はO(n)、クイックソートはO(log n)です。メモリが限られている環境では、ヒープソートのようなO(1)の空間計算量のアルゴリズムが適しています。
実践で活かすためのヒント
1. 適切なアルゴリズムの選択
データサイズと特性に応じて最適なアルゴリズムを選びましょう：
- 小規模データ（n < 100）: 挿入ソート（O(n²)でもOK）
- 中〜大規模データ: マージソート、クイックソート
- 安定性が必要: マージソート
- メモリ制約がある: ヒープソート
2. ライブラリの活用
多くのプログラミング言語では、最適化されたO(n log n)のソート関数が標準ライブラリに含まれています：
- Python:
sorted(),list.sort() - JavaScript:
Array.sort() - Java:
Arrays.sort(),Collections.sort() - C++:
std::sort()
これらは内部でクイックソートやティムソート（マージソート+挿入ソート）を使用しています。
3. ボトルネックの特定
大規模なアプリケーションでは、O(n²)のアルゴリズムがボトルネックになることがあります。プロファイリングツールで計算量の大きい部分を特定し、O(n log n)のアルゴリズムに置き換えることで、劇的な性能改善が期待できます。
まとめ
O(n log n)の線形対数計算量は、実用的なアルゴリズムにおいて最も重要な計算量の一つです。
重要なポイント：
- 比較ベースのソートでは理論的な最良の計算量
- O(n²)よりも圧倒的に速く、大規模データに適している
- マージソート、クイックソート、ヒープソートなど実用的なアルゴリズムで使用
- 分割統治法という重要なアルゴリズム設計手法の代表例
データ構造とアルゴリズムを学ぶ上で、O(n log n)の理解は欠かせません。基本をしっかり押さえて、効率的なプログラミングを目指しましょう。
参考資料
- 『アルゴリズムイントロダクション』Cormen et al.
- 『プログラミングコンテストチャレンジブック』秋葉拓哉ほか
- オンラインジャッジ: AtCoder, LeetCode, Codeforces
関連記事:
- ビッグオー記法の完全ガイド
- データ構造とアルゴリズムの基礎
- ソートアルゴリズムの徹底比較
■らくらくPython塾 – 読むだけでマスター
【現役エンジニア歓迎】プログラミング学習お悩み相談会
【情報I】受験対策・お悩み相談会（オンライン・無料）
【オンライン無料】ゼロから始めるPython爆速講座
■テックジム東京本校
格安のプログラミングスクールといえば「テックジム」。
講義動画なし、教科書なし。「進捗管理とコーチング」で効率学習。
対面型でより早くスキル獲得、月額2万円のプログラミングスクールです。
情報科目の受験対策指導もご用意しております。
