はじめに
- データ構造とアルゴリズムの学習内容を復習し、不足している部分を補うためにここに文章を書いています。
- そのため、誤りが多いと思いますので、間違いを指摘していただけるとありがたいです。
- 機械翻訳を使っているため、不自然な表現があるかもしれません。 これから少しずつ修正していきます。
Big-O
漸近表記法 / asymptotic notation
- Big-O表記法とは、入力サイズが無限大に
n → ∞に近づくときの関数の上限を説明する数学的な表記方法です。 - アルゴリズムの性能を分析する際に最も広く使われる方法であり、理論と実務の両方で基本的な道具として利用されています。
Big-Oの意味
- Big-Oは主に 時間計算量（Time Complexity） を表すために使われます。
- アルゴリズムを実行するのにかかる時間を、入力サイズに対する関数として表します。
- つまり、正確な実行時間よりも、時間の増加傾向が線形なのか？二乗的なのか？ に注目します。
データが大きくなるほど、実行時間がどれくらい速く増加するのか？
表記方法
Big-O表記法には次のような単純化のルールがあります。
- 最高次項だけを残す
- 係数は無視する（例: 3n^2 → n^2）
- 定数項は無視する
Big-O表記法の例
T(n) = 5n² + 3000n + 500
nが無限大に近づくとき（非常に大きな数だとすると）、n²は3000nや500（その他の項）と比べて圧倒的に大きくなります。
したがって、最高次項である 5n² だけを残します。
5n² でも n² でも 増加率 は同じです。
そのため、定数項は無視して n² だけを残します。
n = 1,000,000 のとき 5n² = 5兆、n² = 1兆 → 差は5倍ですが、「二乗的に増加する」という本質は同じです。
係数は実装・環境によって変わり、n→∞ になるほど相対的な意味は小さくなります。
したがって、この関数の Big-O 表記は O(n²) とまとめることができます。
O(1)
- 入力値がどれだけ大きくても、実行時間は一定です。
public int result(int n){
return n * n; // 入力サイズに関係なく常に1回の計算を行う
}
上記の関数のように、n の値がどれだけ大きくても実行時間は一定です。
関連するアルゴリズム
- 配列のインデックスアクセス - arr[6]
- HashMap の .get(key) は平均的に O(1)
- ただし最悪の場合（ハッシュ衝突が多い場合）は O(n)
- スタックの push / pop
- 連結リストの末尾に値を挿入（tail ポインタを持っている場合）
head から末尾まで探索せずに直接挿入可能 - 単純な算術演算
O(log n)
- 入力サイズが大きくなるにつれて実行時間はゆるやかに増加します。
- 各ステップで問題のサイズが半分（あるいは一定の割合）に減少する場合によく現れます。
public int binarySearch(int[] arr, int target) {
int left = 0;
int right = arr.length - 1;
while (left <= right) {
int mid = (left + right) / 2;
if (arr[mid] == target) {
return mid; // 発見
} else if (arr[mid] < target) {
left = mid + 1; // 右半分を探索
} else {
right = mid - 1; // 左半分を探索
}
}
return -1; // 存在しなければ -1 を返す
}
代表的な例として、二分探索は配列の長さが n のとき、探索過程で毎回半分ずつ範囲が減少するため O(log n) の時間がかかります。
関連するアルゴリズム
- 二分探索
- 二分探索木の探索 / 挿入 / 削除（平均的に O(log n)）
- ヒープ（heap）の挿入 / 削除（優先度付きキューの実装時）
- 分割統治アルゴリズム（Merge Sort、Quick Sort）
O(n)
- 入力サイズに比例して線形的に増加します。
- つまり、データが2倍になれば実行時間も2倍になります。
O(n) アルゴリズムは n の大きさに応じて演算を行います。
実行時間が線形に増加するため、O(n) アルゴリズムは「線形時間アルゴリズム」とも呼ばれます。
public int findMax(int[] arr) {
int max = arr[0];
for (int i = 1; i < arr.length; i++) {
if (arr[i] > max) {
max = arr[i];
}
}
return max;
}
- 配列の最大値を求めるためには、すべての要素を一度ずつ確認する必要があります。
- 入力サイズが大きくなるほど実行回数も同じように増えるため、O(n) となります。
関連するアルゴリズム
- 配列 / リストの全体走査（合計の計算、最大値 / 最小値の探索）
- 線形探索（Linear Search）
- ハッシュテーブルの全体走査（すべての値の出力）
- グラフ / 木の探索（BFS, DFS）― ノード数に比例して動作
O(n log n)
- 入力サイズ n 個のデータを処理しつつ、各ステップで log n の時間が必要な場合に現れます。
public class MergeSortExample {
public static void mergeSort(int[] arr) {
if (arr.length <= 1) return;
int mid = arr.length / 2;
int[] left = Arrays.copyOfRange(arr, 0, mid);
int[] right = Arrays.copyOfRange(arr, mid, arr.length);
mergeSort(left); // 半分に分割
mergeSort(right);
merge(arr, left, right); // マージ
}
private static void merge(int[] arr, int[] left, int[] right) {
int i = 0, j = 0, k = 0;
while (i < left.length && j < right.length) {
if (left[i] <= right[j]) {
arr[k++] = left[i++];
} else {
arr[k++] = right[j++];
}
}
while (i < left.length) arr[k++] = left[i++];
while (j < right.length) arr[k++] = right[j++];
}
}
merge sort（マージソート）は、配列を繰り返し半分に分割する過程（log n）と、分割された配列を再び結合する過程（n）が組み合わさることで、全体の時間計算量は O(n log n) となります。
- 比較ベースのソートアルゴリズムは、情報理論的な下限のために平均・最悪の場合 Ω(n log n) より速くなることはできません。
- もちろん入力が最良の場合、比較を省略する最適化を行えば O(n) になることもあります。
- しかしすべてのソートアルゴリズムは、最悪の場合 O(n log n) より速くなることはできません。
- 実用的な観点では、O(n) と O(n log n) は事実上ほぼ同じ性能とみなして差し支えありません。
関連するアルゴリズム
- merge sort
- heap sort
- quick sort（最良・平均の場合 O(n log n)、最悪の場合 O(n²)）
- tim sort（最良の場合 O(n)、平均・最悪の場合 O(n log n)）
- 分割統治アルゴリズム
空間計算量（Space Complexity）
時間計算量と同様に、アルゴリズム分析において重要な要素が空間計算量です。
空間計算量とは、アルゴリズムが実行される間に必要となるメモリ使用量を、入力サイズ n の関数として表したものです。
例えば merge sort を考えてみましょう。
merge sort は配列を繰り返し半分に分割し、再び結合する過程を繰り返します。このとき、元の配列だけでなく、分割した配列を格納するための一時的な配列が必要となります。
- 長さが
nの配列をソートする場合、分割するたびに新しい配列を生成する必要があり → 追加メモリ O(n) - したがって、時間計算量は O(n log n) ですが、空間計算量は O(n) となります。
このように、空間計算量とはアルゴリズムを実行する際に入力データ以外にどれだけ多くのメモリが必要かを示すものです。
O(n²)
- 入力サイズが大きくなるほど、実行時間は二乗で増加します。
- つまり、データが2倍になると実行時間は4倍に増えます。
public void printPairs(int[] arr) {
for (int i = 0; i < arr.length; i++) {
for (int j = 0; j < arr.length; j++) {
System.out.println("(" + arr[i] + ", " + arr[j] + ")");
}
}
}
通常、二重ループ（ネストされた for 文）でよく発生します。
外側のループ : n
内側のループ : n
合計 n * n = n²
関連するアルゴリズム
- バブルソート
- 選択ソート
- 挿入ソート
- ブルートフォース方式（可能なすべてのペア / すべての組み合わせを探索）
O(2ⁿ)
- 入力サイズが n のとき、実行時間は 2 の n 乗に増加します。
- つまり n が少し大きくなるだけでも、実行時間は手に負えないほど大きくなります。
public int fibonacci(int n) {
if (n <= 1) {
return n; // n=0 → 0, n=1 → 1
}
return fibonacci(n - 1) + fibonacci(n - 2);
}
fibonacci(n) を求めるために fibonacci(n-1) と fibonacci(n-2) を再び計算します。
しかし、この2つの関数もそれぞれさらに2つの関数を呼び出すため、呼び出しツリーは二分木のように広がっていきます。
結果的に、呼び出し回数はおおよそ 2ⁿ に比例します。
n が少し大きくなるだけでも、演算回数は指数関数的に増加します。
- n = 10 → 177回の呼び出し
- n = 30 → 200万回以上の呼び出し
したがって、この方法は非常に非効率的であり、このアルゴリズムは別の方法で最適化する必要があります。
関連するアルゴリズム
- 部分集合の生成
- バックトラッキング
- フィボナッチ数列の再帰実装（単純再帰）
O(n!)
- 入力サイズ n のとき、場合の数が階乗（factorial）の数だけ発生し、実行時間が爆発的に増加します。
- 代表的には順列の問題で発生します。
public class PermutationExample {
public void permute(List<Integer> nums, List<Integer> current, boolean[] used) {
if (current.size() == nums.size()) {
System.out.println(current); // 順列を1つ出力する例
return;
}
for (int i = 0; i < nums.size(); i++) {
if (!used[i]) {
used[i] = true;
current.add(nums.get(i));
permute(nums, current, used);
// バックトラッキング（元に戻す処理）
current.remove(current.size() - 1);
used[i] = false;
}
}
}
public static void main(String[] args) {
PermutationExample pe = new PermutationExample();
List<Integer> nums = Arrays.asList(1, 2, 3);
pe.permute(nums, new ArrayList<>(), new boolean[nums.size()]);
}
}
n 個の要素を数列として並べる場合の数は n! になります。
例: n=3 → 3! = 6, n=4 → 24, n=10 → 3,628,800、n=20 → 約 2.4 × 10¹⁸（事実上不可能）。
したがって、順列をすべて生成するアルゴリズムの時間計算量は O(n!) です。
関連アルゴリズムの例
- 順列生成
- 外販員問題（TSP）のブルートフォース解法
- バックトラッキング問題
そのため、O(n!) アルゴリズムは n が10以上になると実用的に使用することはできません。
まとめ
O(1) → O(log n) → O(n) → O(n log n) → O(n²) → O(2ⁿ) → O(n!)
償却分析（Amortized Analysis）
- ある操作は時々非常にコストが高くなるが、ほとんどの場合は非常に安く処理できることがあります。
- このとき「最悪の場合」だけで時間計算量を表すと、実際よりも大げさになります。
- そこで、複数の操作をまとめて平均をとる方法で分析するのが償却分析です。
代表例 : 動的配列
Java の ArrayList を例に考えます。
- ほとんどの場合: O(1) （末尾に要素を追加するだけ）
- ただし、配列がいっぱいになると新しい配列を作成してコピーしなければならないため O(n)
表面的には「最悪の場合 O(n)」と言うべきですが、
実際には n 回の挿入のうち配列コピーが発生するのは数回だけなので、平均的には O(1) と見なせます。
償却分析でこれを証明すると、ArrayList.add() の時間計算量は Amortized O(1) となります。
// アルゴリズム A: バブルソート - O(n²)
public class BubbleSort {
public static void bubbleSort(int[] arr) {
int n = arr.length;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
// swap
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
}
}
// アルゴリズム B: マージソート - O(n log n)
public class MergeSort {
public static void mergeSort(int[] arr) {
if (arr.length <= 1) return;
mergeSortRecursive(arr, 0, arr.length - 1);
}
private static void mergeSortRecursive(int[] arr, int left, int right) {
if (left >= right) return;
int mid = (left + right) / 2;
mergeSortRecursive(arr, left, mid);
mergeSortRecursive(arr, mid + 1, right);
merge(arr, left, mid, right);
}
private static void merge(int[] arr, int left, int mid, int right) {
int[] temp = new int[right - left + 1];
int i = left, j = mid + 1, k = 0;
while (i <= mid && j <= right) {
if (arr[i] <= arr[j]) temp[k++] = arr[i++];
else temp[k++] = arr[j++];
}
while (i <= mid) temp[k++] = arr[i++];
while (j <= right) temp[k++] = arr[j++];
System.arraycopy(temp, 0, arr, left, temp.length);
}
}
n = 50 の場合:
A = 0.5 * 50² = 1250
B = 100 * 50 * log₂(50) ≈ 28,219 （log₂(50) ≈ 5.64）
Big-O で見ると B の方が良いアルゴリズムですが、実際には A よりも22倍遅いことになります。
実務では n は無限大ではなく、多くても「数十万、数千万」程度にとどまります。
さらに、DB インデックスの選択やキャッシュ構造など、他の要素が定数係数として影響します。
そのため Big-O が良いからといって、必ずしも実際に速いとは限りません。
例:
- ハッシュテーブルは理論的には O(1) ですが、衝突が多ければ O(n) レベルの性能低下が発生します。
- B-Tree インデックスは O(log n) ですが、実際にはディスク I/O やキャッシュ効率によって定数係数が変化し、体感性能に大きな差を生じます。
参考資料
자바 알고리즘 인터뷰 with 코틀린 - 박상길