計算量の基本！オーダー記法（o記法）入門

計算量の基本！オーダー記法（O記法）入門

はじめに

プログラミングにおいて、「正しく動く」ことはもちろん重要ですが、それと同じくらい、あるいはそれ以上に「効率が良い」ということも重要です。特に、扱うデータが大規模になったり、応答速度が求められるシステムを開発したりする場合、プログラムの効率は性能に直結します。

効率を評価するための指標が「計算量」です。計算量を知ることで、複数のアルゴリズムがあった場合に、どのアルゴリズムがより高速に、より少ないメモリで動作するかを比較検討できます。

しかし、プログラムの実行時間は、コンピュータの性能、プログラミング言語、コンパイラ、さらにはOSの状況など、さまざまな要因によって変動します。全く同じプログラムを動かしても、違うコンピュータで実行すれば、当然かかる時間は異なります。

そこで、実行環境に依存しない、アルゴリズム自体の効率を評価するための抽象的な尺度が必要になります。それが「オーダー記法」、特に最もよく使われる「O記法（ビッグオー記法）」です。

この記事では、計算量とは何かという基本的な概念から始め、O記法がどのようにアルゴリズムの効率を表現するのか、その読み方、代表的な例、そして実際にコードの計算量を分析する方法まで、詳細に解説します。プログラミング初心者の方、これからアルゴリズムやデータ構造を学ぼうとしている方にとって、計算量の基礎をしっかりと理解するための一歩となることを目指します。

1. 計算量とは何か？

計算量とは、プログラムやアルゴリズムが、与えられた入力を処理するために必要とするリソースの量を測る指標です。主に以下の二つの側面があります。

時間計算量 (Time Complexity):
プログラムが完了するまでにかかる「時間」を測ります。ただし、前述の通り物理的な時間（秒など）ではなく、入力サイズに対してプログラムが実行する基本的な「操作」の回数で評価します。これは、CPUの速度などの実行環境に依存しない、アルゴリズム固有の性質を捉えるためです。
「基本的な操作」とは、変数への代入、算術演算（足し算、引き算など）、比較、配列の要素へのアクセスなど、コンピュータが一度に行える単純な処理を指します。これらの操作にかかる時間は、入力サイズに関わらず一定であると仮定します。
空間計算量 (Space Complexity):
プログラムの実行中に必要とする「メモリ」の量を測ります。具体的には、変数の確保、データ構造（配列、リスト、ツリーなど）に必要な領域、関数呼び出しのスタックなどが含まれます。これも、具体的なバイト数ではなく、入力サイズに対する必要なメモリ領域の増加傾向で評価します。

通常、「計算量」という言葉だけが使われる場合、時間計算量を指すことが多いです。この記事でも、特に断りがない限り、時間計算量を中心に話を進めます。

2. なぜ計算量を評価する必要があるのか？

計算量を評価することには、いくつかの重要な理由があります。

アルゴリズムの比較: 同じ問題を解決する複数のアルゴリズムがある場合、どちらがより効率的かを知るために計算量を比較します。例えば、データをソートするアルゴリズムには、バブルソート、クイックソート、マージソートなど様々なものがありますが、それぞれ計算量が異なります。
性能の予測: 入力サイズが大きくなったときに、プログラムの実行時間がどの程度増加するかを予測できます。これにより、「このアルゴリズムは、データ数が100万件になるとどれくらい時間がかかるか？」といった問いに答える手がかりが得られます。
リソースの最適化: 限られた時間やメモリのリソース内で問題を解決するために、計算量のより良いアルゴリズムを選択したり、既存のアルゴリズムを改善したりする指針となります。
問題の限界の理解: ある種の問題は、どんなアルゴリズムを使っても膨大な計算量が必要となることが分かっています（例：NP困難問題）。計算量を学ぶことは、そのような問題の難しさを理解し、現実的なアプローチ（例：近似解法）を検討する上でも役立ちます。

3. 計算量の測り方：ステップ数のカウント

計算量を測る最も基本的な方法は、プログラムが実行する基本的な操作（ステップ）の数を数えることです。このステップ数は、入力の「サイズ」に関数として依存します。入力サイズは、配列の要素数、文字列の長さ、グラフの頂点数など、問題によって異なりますが、一般的に n という変数で表されます。

簡単な例を見てみましょう。

例1：配列の全要素の合計を計算する

python def sum_array(arr): total = 0 # ステップ1: 代入 (O(1)操作) for x in arr: # ステップ2: ループ開始。配列の長さが n とすると、ループ本体は n 回実行される total += x # ステップ3: 加算と代入 (O(1)操作)。これが n 回実行される return total # ステップ4: 返却 (O(1)操作)

この関数 sum_array の実行ステップ数を数えてみます。
* total = 0 は1ステップです。
* for x in arr: ループは、配列 arr の要素数（入力サイズ n）だけ繰り返されます。
* ループの中で実行される total += x は、代入と加算の組み合わせで、これも基本的な操作として1ステップと見なせます。これが n 回実行されます。
* return total は1ステップです。

したがって、全体のステップ数は、おおよそ $1 + n \times 1 + 1 = n + 2$ ステップとなります。

例2：入れ子になったループ

python def count_pairs(arr): n = len(arr) count = 0 # ステップ1: 代入 (O(1)) for i in range(n): # ステップ2: 外側のループ開始。n 回実行 for j in range(n): # ステップ3: 内側のループ開始。外側のループの1回につき n 回実行されるので、合計 n * n 回実行される if arr[i] == arr[j]: # ステップ4: 比較 (O(1))。これが n*n 回実行される count += 1 # ステップ5: 加算と代入 (O(1))。これも n*n 回実行される return count # ステップ6: 返却 (O(1))

この関数のステップ数はどうなるでしょうか。
* n = len(arr) と count = 0 はそれぞれO(1)ステップです。
* 外側のループは n 回実行されます。
* 内側のループは、外側のループが1回実行されるごとに n 回実行されます。したがって、内側のループ全体としては n * n = n^2 回実行されます。
* 内側のループの中で実行される if arr[i] == arr[j]: と count += 1 は、それぞれO(1)ステップと見なせます。これらが内側のループの回数、つまり n^2 回実行されます。
* return count はO(1)ステップです。

したがって、全体のステップ数は、おおよそ $1 + 1 + n \times (n \times (1 + 1)) + 1 = 2n^2 + 3$ ステップとなります。

このように、ステップ数を数えることで、入力サイズ n に対して計算量がどのように増加するかを関数として表現できます。例1では $n+2$、例2では $2n^2+3$ のように。

4. オーダー記法（漸近記法）とは？

ステップ数を厳密に数える方法は、アルゴリズムの比較には役立ちますが、いくつかの課題があります。

煩雑さ: アルゴリズムが複雑になるほど、正確なステップ数を数えるのは非常に骨が折れる作業になります。
実行環境への依存（細かい点）: 「基本的な操作」にかかる時間は、厳密には一定ではありません。例えば、メモリのキャッシュヒット率によって配列アクセス速度は変わる可能性があります。また、コンパイラの最適化によって、同じコードでも生成される機械語のステップ数は変わりえます。
本質を見失う: $n+2$ と $n+100$ というステップ数のアルゴリズムがあったとき、入力サイズ n が非常に大きくなればなるほど、定数の $+2$ や $+100$ の影響は小さくなり、どちらも「n に比例して増える」という点が支配的になります。同様に、$2n^2+3$ と $5n^2+100$ では、入力サイズが大きくなると $n^2$ の項が支配的になり、「n^2 に比例して増える」という性質が重要になります。

ここで登場するのが「オーダー記法」、より正確には「漸近記法」です。漸近記法は、入力サイズ n が非常に大きくなったときの計算量の「増加の傾向」や「振る舞い」を、主要な項だけに着目してシンプルに表現するための記法です。定数係数や、入力サイズが大きくなったときに無視できるような低い次数の項は省略されます。

漸近記法にはいくつかの種類がありますが、アルゴリズムの計算量を表す際によく用いられるのは以下の3つです。

O記法 (ビッグオー記法): 最悪ケース（上界）を表します。「高々〜である」という意味。例えば、$O(n^2)$ は、最悪でも計算量が $n^2$ に比例する程度にしか増加しないことを示します。これは、アルゴリズムの性能保証として最もよく使われます。
Ω記法 (オメガ記法): 最良ケース（下界）を表します。「少なくとも〜である」という意味。例えば、$\Omega(n)$ は、最良でも計算量が n に比例する程度には増加することを示します。
Θ記法 (シータ記法): 平均ケース（タイトな限界）を表します。「〜に比例する」という意味。O記法とΩ記法の両方を満たす場合に用いられます。例えば、$\Theta(n)$ は、計算量が n に比例することを示します。

他に、o記法（スモールオー）やω記法（スモールオメガ）もありますが、これらはO記法やΩ記法よりもさらに厳しい不等式を表すため、アルゴリズムの計算量を議論する際にはO記法が最も一般的です。

この記事では、最も頻繁に登場し、アルゴリズムの効率を語る上で基本となるO記法（ビッグオー記法）に焦点を当てて詳細に解説します。

5. O記法（ビッグオー記法）の詳細

O記法は、アルゴリズムの「最悪の場合の性能」や「増加率の上界」を表すために最も広く使われます。

5.1. O記法の定義

数学的には、関数 $g(n)$ が $O(f(n))$ であるとは、ある正の定数 $c$ と、ある非負の整数 $n_0$ が存在して、すべての $n \ge n_0$ に対して $|g(n)| \le c|f(n)|$ が成り立つこと、と定義されます。

言葉で言うと、入力サイズ n が十分に大きいとき（$n \ge n_0$）、アルゴリズムの実際の計算量 $g(n)$ は、ある定数 $c$ を掛けた $f(n)$ を超えない、ということです。つまり、$f(n)$ は $g(n)$ の「上界」を示す関数となります。

例えば、先ほどの例1の計算量は $n+2$ でした。これは $O(n)$ と表現できます。なぜなら、例えば $c=2$ とすると、$n \ge 2$ のとき、$n+2 \le 2n$ が成り立つからです（実際、$n+2 \le 2n$ は $2 \le n$ と同値）。つまり、$n \ge 2$ の範囲では、$n+2$ は $2n$ を超えません。したがって、$n+2$ は $O(n)$ です。

例2の計算量は $2n^2+3$ でした。これは $O(n^2)$ と表現できます。例えば $c=3$ とすると、$n \ge 2$ のとき、$2n^2+3 \le 3n^2$ が成り立ちます（実際、$2n^2+3 \le 3n^2$ は $3 \le n^2$ と同値であり、$n \ge 2$ なら $n^2 \ge 4$ なので成立）。したがって、$2n^2+3$ は $O(n^2)$ です。

5.2. O記法におけるルールと簡略化

O記法を使う上で重要なのは、定数係数と低い次数の項を無視するという「簡略化」のルールです。これは、入力サイズ n が非常に大きいときに、計算量の増加傾向を支配するのは最も高い次数の項だからです。

定数係数は無視する:
$O(c \times f(n)) = O(f(n))$
例: $O(5n) = O(n)$, $O(3n^2) = O(n^2)$, $O(100) = O(1)$
理由: 定数 $c$ は、入力サイズ n の増加率には影響しません。グラフで見ると、関数全体の傾きは変わりますが、増加のカーブの形（線形、二次など）は同じです。O記法は増加の「形」に注目します。
低い次数の項は無視する:
$O(f(n) + g(n))$ において、$f(n)$ が $g(n)$ よりも入力サイズ n の増加に対してはるかに速く増加する場合、$O(f(n) + g(n)) = O(f(n))$
例: $O(n^2 + n) = O(n^2)$, $O(n^3 + 2n^2 + 1000) = O(n^3)$, $O(n + \log n) = O(n)$
理由: n が非常に大きいとき、$n^2$ は $n$ に比べて圧倒的に大きくなります。例えば、$n=1000$ のとき、$n^2 = 1,000,000$ に対して $n=1000$ であり、$n^2$ の方がはるかに支配的です。O記法は「漸近的な振る舞い」に注目するため、支配的な項以外は無視します。

これらのルールを適用すると、先ほどの例の計算量は以下のように簡略化できます。
* 例1 ($n+2$): 定数項 +2 を無視し、係数 1 を無視すると $O(n)$ となります。
* 例2 ($2n^2+3$): 定数項 +3 を無視し、低い次数の項がないので係数 2 を無視すると $O(n^2)$ となります。

5.3. 代表的なオーダーと計算量の比較

よく登場する代表的なオーダーを、計算量の小さい順（効率が良い順）に並べ、それぞれの特徴と例を見てみましょう。

$O(1)$ – 定数時間 (Constant Time)
- 入力サイズ n に関係なく、実行時間が一定。最も効率が良い。
- 例:
  - 配列の特定のインデックスへのアクセス（arr[i]）
  - ハッシュテーブル（ハッシュマップ）でのデータの挿入、削除、検索（理想的なハッシュ関数と衝突解決ができた場合）
  - 変数の代入、算術演算、比較などの基本的な命令
$O(\log n)$ – 対数時間 (Logarithmic Time)
- 入力サイズ n が増加するにつれて、実行時間は非常にゆっくり増加する。効率が良い。
- 例:
  - ソートされた配列に対する二分探索 (Binary Search)
  - 平衡二分探索木 (Balanced Binary Search Tree) の操作（挿入、削除、検索）
- なぜ「対数」なのか？問題空間を分割して処理するアルゴリズムでよく現れます。二分探索では、検索範囲が毎回半分になるため、サイズ n の範囲から1つの要素を見つけるのに必要な分割回数は $\log_2 n$ に比例します。O記法では対数の底は省略されることが多いです（$O(\log_a n) = O(\log_b n)$ because $\log_b n = \frac{\log_a n}{\log_a b}$ and $\frac{1}{\log_a b}$ is a constant）。
$O(n)$ – 線形時間 (Linear Time)
- 入力サイズ n に比例して実行時間が増加する。
- 例:
  - 配列や連結リストの全要素を一度だけ走査する処理（合計値の計算、最大値の探索など）
  - ソートされていない配列に対する線形探索 (Linear Search)
  - 単一のループで入力サイズの回数だけ処理を行う場合
$O(n \log n)$ – 線形対数時間 (Linearithmic Time)
- $O(n)$ よりは遅いが、$O(n^2)$ よりは十分に速い。効率の良いソートアルゴリズムに多く見られる。
- 例:
  - マージソート (Merge Sort)
  - クイックソート (Quick Sort) の平均ケース
  - ヒープソート (Heap Sort)
- これは、配列を分割して再帰的に処理し、その後にマージや統合を行うようなアルゴリズム（分割統治法）でよく現れます。例えばマージソートは、配列を半分に分割する処理（$\log n$ 回の分割レベル）と、それぞれのレベルで配列全体をマージする処理（各レベルで合計 $O(n)$）を組み合わせた結果、$O(n \log n)$ となります。
$O(n^2)$ – 二次時間 (Quadratic Time)
- 入力サイズ n の二乗に比例して実行時間が増加する。入力サイズが大きくなると急激に遅くなる。
- 例:
  - 二重の入れ子になったループで、内側のループが外側のループのサイズに依存しない場合
  - バブルソート (Bubble Sort)、選択ソート (Selection Sort)、挿入ソート (Insertion Sort) の最悪ケース・平均ケース
  - 全ての要素ペアを比較する処理
$O(n^3)$ – 三次時間 (Cubic Time)
- 入力サイズ n の三乗に比例して実行時間が増加する。三重の入れ子ループなどで現れる。
- 例:
  - 三重の入れ子になったループ
  - 単純な行列の乗算アルゴリズム
$O(2^n)$ – 指数時間 (Exponential Time)
- 入力サイズ n に対して、実行時間が指数関数的に増加する。非常に効率が悪く、少しでも入力サイズが大きくなると現実的な時間で完了しない。
- 例:
  - 巡回セールスマン問題 (Traveling Salesperson Problem) の全探索（総当たり）
  - 組み合わせ最適化問題の全探索
  - メモ化（動的計画法）を用いない素朴な再帰によるフィボナッチ数列の計算
$O(n!)$ – 階乗時間 (Factorial Time)
- 入力サイズ n の階乗に比例して実行時間が増加する。$O(2^n)$ よりもさらに増加率が大きく、最も効率が悪いオーダーの一つ。
- 例:
  - 全ての順列を生成するアルゴリズム（総当たり）

これらのオーダーをグラフで比較すると、その増加率の違いがよく分かります。

$O(1)$ は横一直線
$O(\log n)$ は非常に緩やかな増加
$O(n)$ は直線的な増加
$O(n \log n)$ は $O(n)$ より少し速い増加
$O(n^2)$ は放物線のような急激な増加
$O(n^3)$ はさらに急激な増加
$O(2^n)$ や $O(n!)$ は、ごく小さな n を超えると爆発的に増加します。

ほとんどの場合、$O(n \log n)$ までのオーダーのアルゴリズムが実用的とされます。$O(n^2)$ やそれ以上のオーダーのアルゴリズムは、入力サイズが小さい場合にのみ使われるか、より効率の良いアルゴリズムが存在しない場合にやむを得ず使われることがあります。

5.4. 計算量の種類：最良ケース、平均ケース、最悪ケース

O記法は通常、「最悪ケース (Worst Case)」の計算量を記述するのに使われます。最悪ケースとは、入力データがアルゴリズムにとって最も不利な状況になる場合の性能です。例えば、線形探索で探している要素が配列の最後にあったり、配列に全く存在しなかったりする場合が最悪ケースです。

なぜ最悪ケースを重視するのでしょうか？それは、最悪ケースの計算量が分かれば、そのアルゴリズムがどんな入力データに対しても少なくともその性能は保証できる、という安心感があるからです。

ただし、アルゴリズムによっては、最悪ケースの計算量が非常に悪くても、平均的にはずっと高速に動作するものがあります。例えば、クイックソートの最悪ケースは $O(n^2)$ ですが（入力がほとんどソートされている場合など）、平均ケースは $O(n \log n)$ と非常に効率が良いです。

最悪ケース (Worst Case): 最も計算コストが高くなる入力に対する性能。O記法 ($O$) で表現されることが多い。
最良ケース (Best Case): 最も計算コストが低くなる入力に対する性能。Ω記法 ($\Omega$) で表現されることが多い。例えば、線形探索で探している要素が配列の最初の要素である場合、最良ケースは $O(1)$ です。
平均ケース (Average Case): 考えられる全ての入力に対する平均的な性能。Θ記法 ($\Theta$) で表現されることが多い。平均ケースの分析は、入力データの分布を仮定する必要があるため、難しい場合があります。

一般的に、アルゴリズムの計算量を「O記法で $f(n)$」と言う場合、特に断りがなければ最悪ケースの計算量が $O(f(n))$ であることを指すことが多いです。しかし、文脈によっては平均ケースを指すこともあるため、曖昧さを避けるためには「最悪ケースの計算量は $O(f(n))$ です」のように明記するのが丁寧です。

6. 具体的なコード例で計算量を分析する

いくつかのプログラミングの基本的な操作やコード構造について、O記法を用いた計算量分析の例を見てみましょう。（ここではPythonを例にしますが、概念は他の言語でも同様です。）

例1：配列の合計値を計算（再掲）

python def sum_array(arr): total = 0 # 配列 arr のサイズを n とする for x in arr: # ループは n 回実行される total += x # ループ内で定数時間 (O(1)) の操作 return total
* total = 0: O(1)
* for ループ: n 回繰り返される。
* total += x: ループ内で1回あたり O(1)。合計 $n \times O(1) = O(n)$。
* return total: O(1)

全体の計算量: $O(1) + O(n) + O(1) = O(n)$。定数項や低い次数の項は無視するので、最終的に $O(n)$ となります。

例2：特定の要素が配列に存在するか線形探索

python def linear_search(arr, target): # 配列 arr のサイズを n とする for x in arr: # ループは最大 n 回実行される if x == target: # ループ内で定数時間 (O(1)) の比較 return True # 見つかったら即座に終了 (O(1)) return False # 見つからなかった場合 (O(1))
* 最良ケース: ターゲットが最初の要素にある場合。ループ1回目で終了。$O(1)$。
* 最悪ケース: ターゲットが最後の要素にあるか、全く存在しない場合。ループが n 回全て実行される。$n \times O(1) + O(1) = O(n)$。
* 平均ケース: ターゲットが平均的に真ん中あたりで見つかると仮定すると、約 $n/2$ 回のループが必要。$O(n)$。

線形探索の計算量は、通常最悪ケースで $O(n)$ と表現されます。

例3：入れ子になったループ（再掲）

python def nested_loops(arr): n = len(arr) count = 0 # 外側のループは n 回 for i in range(n): # 内側のループは、外側のループの各反復で n 回 for j in range(n): # 内側のループ内で定数時間 (O(1)) の操作 if arr[i] == arr[j]: count += 1 return count
* 外側のループ: n 回
* 内側のループ: 外側のループの各回につき n 回。合計 $n \times n = n^2$ 回。
* 内側のループ内の操作 (if, +=): 1回あたり O(1)。合計 $n^2 \times O(1) = O(n^2)$。

全体の計算量: $O(n^2)$。

もし内側のループが range(i, n) のように、外側のループ変数 i に依存する場合、合計の繰り返し回数は $n + (n-1) + \dots + 1 = n(n+1)/2$ となります。これは $0.5n^2 + 0.5n$ ですが、O記法では定数係数と低い次数の項を無視するので、これも $O(n^2)$ となります。

例4：二分探索 (Binary Search)

“`python
def binary_search(arr, target):
# ソートされた配列 arr のサイズを n とする
low = 0
high = len(arr) – 1

while low <= high: # ループ
    mid = (low + high) // 2 # O(1)
    if arr[mid] == target: # O(1)
        return mid # O(1)
    elif arr[mid] < target: # O(1)
        low = mid + 1 # O(1)
    else: # O(1)
        high = mid - 1 # O(1)

return -1 # O(1)

`` 二分探索では、検索範囲がループ1回ごとに約半分になります。サイズnのリストを半分にし続けると、サイズが1になるまでに必要な分割回数は $\log_2 n$ に比例します。例えば、サイズ 16 のリストは $16 \to 8 \to 4 \to 2 \to 1$ と4回分割します。$\log_2 16 = 4$ です。ループ内の操作（midの計算、比較、low/high` の更新）は全て O(1) です。
ループの繰り返し回数は O($\log n$)。
したがって、全体の計算量は $O(\log n) \times O(1) = O(\log n)$ となります。

例5：フィボナッチ数列の計算（再帰、メモ化なし）

python def fibonacci_recursive(n): if n <= 1: # O(1) return n # O(1) else: # 2つの再帰呼び出し return fibonacci_recursive(n-1) + fibonacci_recursive(n-2)
fibonacci_recursive(n) を計算するためには、fibonacci_recursive(n-1) と fibonacci_recursive(n-2) を計算する必要があります。これらの呼び出しはさらに分岐し、計算の木は指数関数的に広がります。例えば、fibonacci_recursive(5) は fibonacci_recursive(4) と fibonacci_recursive(3) を呼び出し、fibonacci_recursive(4) は fibonacci_recursive(3) と fibonacci_recursive(2) を呼び出し、… のように、同じ計算が何度も繰り返されます。
この再帰ツリーのノード数は、おおよそ $2^n$ に比例します。したがって、計算量は $O(2^n)$ となります。非常に効率が悪いです。

例6：フィボナッチ数列の計算（繰り返し、またはメモ化）

“`python
def fibonacci_iterative(n):
if n <= 1: # O(1)
return n # O(1)

a, b = 0, 1 # O(1)
# 2から n までの n-1 回のループ
for _ in range(2, n + 1):
    # ループ内で定数時間 (O(1)) の操作
    a, b = b, a + b
return b # O(1)

`` この反復バージョンでは、各フィボナッチ数を計算するために、直前の2つの数を利用します。各ステップで O(1) の計算を行い、それをn-1` 回繰り返します。
全体の計算量は $O(1) + O(1) + (n-1) \times O(1) + O(1) = O(n)$ となります。
例5の $O(2^n)$ と比較して、繰り返し（またはメモ化による動的計画法）を使うことで計算量が劇的に改善されることが分かります。

7. 空間計算量 (Space Complexity)

時間計算量と同様に、アルゴリズムが使用するメモリ量も O記法で表現できます。空間計算量も、入力サイズ n の関数として表されます。

$O(1)$ – 定数空間:
- 入力サイズに関係なく、使用するメモリ量が一定。変数をいくつか使うだけの場合など。
- 例: 例1の sum_array 関数（total 変数だけを使う）、例6の fibonacci_iterative 関数（a, b 変数だけを使う）。
$O(n)$ – 線形空間:
- 入力サイズ n に比例して使用するメモリ量が増加する。入力のコピーを作成したり、入力サイズの配列やリストを追加で作成したりする場合など。
- 例:
  - 入力配列の全ての要素をコピーして新しい配列を作成する関数。
  - 一部のソートアルゴリズム（例：マージソートは結果を格納するために O(n) の追加空間を必要とする）。
  - 例5の再帰的なフィボナッチ関数。関数の再帰呼び出しの深さが最大 n となるため、コールスタックに O(n) の領域が必要になります。
$O(n^2)$ – 二次空間:
- 入力サイズ n の二乗に比例して使用するメモリ量が増加する。n x n の二次元配列（行列）を作成する場合など。

空間計算量は、特に利用可能なメモリが限られている環境（組み込みシステムなど）や、非常に大規模なデータを扱う場合に重要になります。時間計算量が優れていても、要求されるメモリ量が膨大であれば、そのアルゴリズムは実用的ではない可能性があります。

8. O記法を使う上での注意点・限界

O記法はアルゴリズムの効率を評価する上で非常に強力なツールですが、いくつかの注意点と限界があります。

定数係数と低次項の影響: O記法はこれらを無視しますが、実際の実行時間には影響します。例えば、$O(n)$ のアルゴリズムでも、ステップ数が $100n$ のものと $2n$ のものでは、後者の方が圧倒的に高速です。入力サイズがそれほど大きくない場合、$O(n^2)$ のアルゴリズムでも、定数係数が小さければ $O(n \log n)$ のアルゴリズムより高速になることもあります。
例：小さな配列に対する挿入ソート（O(n^2)）は、マージソート（O(n log n)）よりも高速である場合があります。これは、挿入ソートの定数係数が小さく、オーバーヘッドが少ないためです。
入力サイズが小さい場合: O記法は入力サイズが「十分に大きい」ときの漸近的な振る舞いを表します。入力サイズが非常に小さい場合は、オーダーの良い悪いよりも、コードの単純さや定数係数の方が影響が大きいことがあります。
ハードウェア特性の無視: CPUのキャッシュ、メモリ階層、並列処理能力などは、O記法では考慮されません。例えば、同じ $O(n)$ の計算量でも、データのアクセスパターンによってキャッシュの利用効率が異なり、実際の実行速度に差が出ることがあります。
O記法は最悪ケースを表すことが多い: 前述の通り、O記法は最悪ケースを表すことが一般的ですが、アルゴリズムによっては最悪ケースは稀にしか発生せず、平均ケースの方がはるかに効率が良い場合もあります。アルゴリズムを選択する際には、どのケースの計算量を見るべきか、そのアルゴリズムの典型的な入力パターンはどうなるかを考慮する必要があります。

これらの限界があるからといって、O記法が無意味なわけではありません。O記法は、多数のデータが与えられたときに「スケールするかどうか」、つまり入力サイズが大きくなったときに性能劣化がどの程度抑えられるか、を判断するための最も基本的なツールです。アルゴリズム設計や選択の最初のステップとして、オーダーによる評価は不可欠です。実際のシステムでは、O記法による評価で大まかな絞り込みを行った後、より詳細な分析やベンチマーク（実際にコードを実行して時間を測る）を行うのが一般的です。

9. まとめ

この記事では、計算量の基本、特にオーダー記法（O記法）に焦点を当てて解説しました。

計算量は、アルゴリズムの効率を測る指標であり、主に時間計算量と空間計算量があります。これは実行環境に依存しない、アルゴリズム自体の性能を評価するために重要です。
計算量は、入力サイズ n に対する基本的な操作のステップ数やメモリ使用量として評価されます。
オーダー記法（O記法）は、入力サイズが十分に大きいときの計算量の「漸近的な振る舞い」を抽象的に表現するための記法です。定数係数や低い次数の項は無視されます。
O記法は通常、アルゴリズムの最悪ケースの計算量（上界）を表すために使われます。
代表的なオーダーには、$O(1), O(\log n), O(n), O(n \log n), O(n^2), O(2^n), O(n!)$ などがあり、これらは効率の良い順に並んでいます。オーダーの違いは、入力サイズが大きくなったときに実行時間がどれだけ急激に増加するかに大きく影響します。
コードの計算量を分析するには、ループ構造や再帰呼び出しに着目し、入力サイズ n に対して基本的な操作が何回実行されるかを数え、O記法のルールに従って簡略化します。
O記法には限界もありますが、アルゴリズムの効率を理解し、より良いアルゴリズムを選択するための強力な第一歩となります。

計算量の概念とO記法を理解することは、効率的なプログラムを書くため、データ構造やアルゴリズムを学ぶ上で不可欠な基礎知識です。ぜひ、様々なアルゴリズムやデータ構造の計算量を自分で分析する練習をしてみてください。

10. さらに学ぶには

O記法は計算量分析の入り口です。さらに深く学びたい場合は、以下のトピックを調べてみてください。

他の漸近記法: Ω記法、Θ記法、o記法、ω記法の厳密な定義とその使い分け。
償却計算量 (Amortized Analysis): 一回の操作の最悪ケースは大きいが、連続した操作の合計コストを操作回数で割った平均が小さい場合の計算量評価（例：動的配列への要素追加など）。
具体的なデータ構造とアルゴリズムの計算量: 配列、連結リスト、スタック、キュー、ツリー、グラフ、ハッシュテーブルなどのデータ構造の操作や、様々なソート・探索アルゴリズムの詳細な計算量分析。
計算量クラス: 問題自体の難しさを分類する概念（P問題、NP問題、NP完全問題など）。

計算量というレンズを通してアルゴリズムを見ることで、プログラムの性能に対する理解が格段に深まるはずです。頑張ってください！