はじめに
技術書を読んだり、アルゴリズムを勉強したりしていると、さも当然のように現れるビッグ・オー (Big-O) 記法についての備忘録です。
改訂履歴
- 2026/10/01 : 初版公開。
本文
1. 概要
ビッグ・オー (Big-O) 記法は、アルゴリズムの計算量が入力サイズに対してどのように増加するかを表すための記法です。数学的には、ランダウの記号 (Landau symbol) の一つとして定義されます。
例えば、入力の要素数を n としたとき、
-
O(1)：入力サイズに関係なく、ほぼ一定の時間で処理できる -
O(log n)：入力サイズが増えても、処理量の増加は緩やか -
O(n)：入力サイズに比例して処理量が増える -
O(n log n)：nよりは増えるが、n²よりは緩やか -
O(n²)：入力サイズの二乗に比例して処理量が増える
といった具合に表現します。
log とは対数のことで「ある数を何乗すると目的の数になるか」を表します。例えば log₂ 8 = 3 は「2 を 3 回かけると 8 になる」という意味です。計算量の世界では log n は log₂ n とみなすことが多く、入力サイズが 2 倍になるたびに、必要な処理回数が 1 回程度増えるような計算量を表します。例えば n = 2 なら log₂ 2 = 1、n = 4 なら log₂ 4 = 2、n = 8 なら log₂ 8 = 3、n = 16 なら log₂ 16 = 4 となります。
ここで重要なのは、ビッグ・オー記法が実際に何秒かかるかを直接表しているわけではない、という点です。主に、入力サイズ n が大きくなったときに計算量がどの程度の割合で増えていくのか、つまりアルゴリズムの漸近的な増加傾向を表します。
例えば、あるアルゴリズムの処理回数が 3n² + 10n + 5 だったとします。ここで n が 1,000,000,000 といった十分に大きな数値になると、n² の項が他の項に比べて支配的になります。そのため、ビッグ・オー記法のルールでは定数倍や低次の項を無視して、O(n²) と表します。この大きな入力に対して、どの項が支配的になるかを見るという考え方が、ビッグ・オー記法を理解するうえでの基本になります。
なお、ビッグ・オー記法は一般にアルゴリズムの「時間計算量」を説明するために使われますが、メモリ使用量などの「空間計算量」を表す場合にも使われます。
アルゴリズムを比較する際には、単純に O(n) のほうが O(n²) より速い、と考えるだけでは不十分です。実際の実行時間には、定数倍、入力データの性質、ハードウェア、実装方法なども影響します。
2. 種類
2-1. O(1)
入力サイズ n が増えても、処理量が一定の計算量です。例えば、配列の i 番目の要素を取得する処理などが該当します。
// 要素取得。
int GetElement(int[] array, int index)
{
return array[index];
}
2-2. O(log n)
入力サイズ n が増えるにつれて処理量も増えますが、その増加は非常に緩やかな計算量です。代表的な例として、二分探索があります。
// 二分探索。
// ※ array の中身が昇順にソートされていることが前提。
int BinarySearch(int[] array, int target)
{
int left = 0;
int right = array.Length - 1;
while (left <= right)
{
int middle = left + (right - left) / 2;
if (array[middle] == target)
{
return middle;
}
if (array[middle] < target)
{
left = middle + 1;
}
else
{
right = middle - 1;
}
}
return -1;
}
2-3. O(n)
入力サイズ n に比例して処理量が増える計算量です。最悪の場合、配列の全て要素を調べる必要があります。代表的な例には、配列の全体走査や線形探索があります。
// 線形探索。
int LinearSearch(int[] array, int target)
{
for (int i = 0; i < array.Length; i++)
{
if (array[i] == target)
{
return i;
}
}
return -1;
}
2-4. O(n log n)
入力サイズ n と log n をかけ合わせた形で増加する計算量です。例えば、入力サイズ n 個のデータに対して、各データの処理に log n の時間が必要な場合などに現れます。最も代表的な例はマージソート、ヒープソート、平均的なクイックソート（クイックソートは最悪の場合 O(n²) になる）です。
// マージソート。
int[] MergeSort(int[] array)
{
if (array.Length <= 1)
{
return array;
}
int middle = array.Length / 2;
int[] left = array[..middle];
int[] right = array[middle..];
left = MergeSort(left);
right = MergeSort(right);
return Merge(left, right);
}
// ソート済の配列をマージする。
int[] Merge(int[] left, int[] right)
{
int[] result = new int[left.Length + right.Length];
int i = 0;
int j = 0;
int k = 0;
while (i < left.Length && j < right.Length)
{
if (left[i] <= right[j])
{
result[k++] = left[i++];
}
else
{
result[k++] = right[j++];
}
}
while (i < left.Length)
{
result[k++] = left[i++];
}
while (j < right.Length)
{
result[k++] = right[j++];
}
return result;
}
O(n log n) は、代表的な効率の良い比較ベース（要素同士を比較することを基本的な操作とする）のソートアルゴリズムで現れる計算量です。
2-5. O(n²)
入力サイズ n の 2 乗に比例して処理量が増える計算量です。例えば、全ての要素の組み合わせを調べる処理などが該当します。実務だといわゆる 2 重ループ（ネストされた for 文）でよく表れると思います。O(n²) の代表例はバブルソート、選択ソート、挿入ソートなどになります。
// バブルソート。
void BubbleSort(int[] array)
{
for (int i = 0; i < array.Length - 1; i++)
{
for (int j = 0; j < array.Length - 1 - i; j++)
{
if (array[j] > array[j + 1])
{
(array[j], array[j + 1]) = (array[j + 1], array[j]);
}
}
}
}
2-6. O(2ⁿ)
入力サイズ n が 1 増えるたびに、処理量が約 2 倍になる計算量です。代表的な例として、単純な再帰によってフィボナッチ数列を計算する処理や、全ての部分集合を列挙する処理などがあります。
// 部分集合。
// ※このコード全体の、実際の時間計算量は O(n × 2ⁿ)。
void GenerateSubsets(int[] array)
{
int count = 1 << array.Length;
for (int mask = 0; mask < count; mask++)
{
for (int i = 0; i < array.Length; i++)
{
// 各要素について true / false の 2 通りがあるため、部分集合は 2ⁿ。
// もし 3 通りの選択肢があれば、3ⁿ 通りになる。
if ((mask & (1 << i)) != 0)
{
Console.Write($"{array[i]} ");
}
}
Console.WriteLine();
}
}
2-7. O(n!)
入力サイズ n の階乗に比例して処理量が増える計算量です。代表的な例として、n 個の要素から全ての順列を生成する処理があります。
// 順列生成。
// ※このコード全体の、実際の時間計算量は O(n × n!)。
void Permute(int[] array, int start)
{
if (start == array.Length)
{
Console.WriteLine(string.Join(" ", array));
return;
}
for (int i = start; i < array.Length; i++)
{
(array[start], array[i]) = (array[i], array[start]);
Permute(array, start + 1);
(array[start], array[i]) = (array[i], array[start]);
}
}
2-8. 比較
入力サイズ n に対する各計算量の関数値は以下のようになります。O(2ⁿ) や O(n!) は、n の増加に対する値の増え方が凄まじいですね。
n |
O(1) |
O(log n) |
O(n) |
O(nlog n) |
O(n²) |
O(2ⁿ) |
O(n!) |
|---|---|---|---|---|---|---|---|
| 1 | 1 | 0 | 1 | 0 | 1 | 2 | 1 |
| 2 | 1 | 1 | 2 | 2 | 4 | 4 | 2 |
| 4 | 1 | 2 | 4 | 8 | 16 | 16 | 24 |
| 8 | 1 | 3 | 8 | 24 | 64 | 256 | 40,320 |
| 16 | 1 | 4 | 16 | 64 | 256 | 65,536 | 約2.1×10¹³ |
| 32 | 1 | 5 | 32 | 160 | 1,024 | 約4.3×10⁹ | 約2.6×10³⁵ |
| 64 | 1 | 6 | 64 | 384 | 4,096 | 約1.8×10¹⁹ | 約8.3×10⁸⁹ |
| 128 | 1 | 7 | 128 | 896 | 16,384 | 約3.4×10³⁸ | 約3.9×10²¹⁵ |
おわりに
気付きがあれば、追記します。