【ITニュース解説】Big O Notation: Examples

システムエンジニアを目指す上で、プログラムの効率を理解することは非常に重要である。その効率を示す指標の一つが「Big O記法（ビッグオー記法）」だ。これは、プログラムが扱うデータの量（入力サイズ n）が増えたときに、そのプログラムの実行時間や使用するメモリがどのように増えるかを示すもので、特に「最悪の場合」の効率を表す。プログラムの設計段階でBig O記法を考慮することで、大規模なデータや多くのユーザーが利用するシステムでも問題なく動作する、高性能なソフトウェアを開発できるようになる。

まず、最も効率が良いとされるのが「O(1) 定数時間」だ。これは、入力データのサイズに関わらず、処理にかかる時間が常に一定であることを意味する。例えば、配列の最初の要素を取得するような操作がこれに当たる。配列に10個のデータがあっても100万個のデータがあっても、先頭の要素を取り出すのにかかる時間は変わらないため、非常に効率的である。

次に、入力データ量 n に比例して処理時間が増える「O(n) 線形時間」がある。これは、配列のすべての要素を順番に調べて特定の値を探す「線形探索」のような処理が典型的な例だ。もし目的の値が配列の最後にあったり、そもそも配列になかったりする「最悪のケース」では、すべての要素を一つずつ確認しなければならないため、データの数に比例して時間がかかる。

効率の面でO(n)よりも優れているのが「O(log n) 対数時間」である。これは、入力データ量 n が増えても処理時間の増加が非常に緩やかであることを示す。代表的な例は、ソート（並び替え）された配列の中から特定の値を効率よく探す「二分探索」だ。このアルゴリズムでは、探索範囲を毎回半分に絞り込んでいくため、データの数が倍になっても、処理にかかる時間はわずかしか増えない。例えば、100万個のデータから探す場合でも、たかだか20回程度の比較で済む。

「O(n log n)」は、O(n)とO(log n)の中間に位置し、効率の良いソートアルゴリズムによく見られる。例えば、「マージソート」というソートアルゴリズムは、配列を半分に分割し、それぞれをソートしてから再び結合するという処理を繰り返す。この「分割して、それぞれをソートし、結合する」というプロセスが全体として O(n log n) の効率を生み出す。多くの要素を効率的に並べ替える必要がある場合に利用される。

一方、効率が悪いとされるのが「O(n²) 二乗時間」だ。これは、入力データ量 n の二乗に比例して処理時間が増えることを意味し、二重ループのような処理でよく発生する。例えば、配列内のすべての要素のペアを調べて何かをする場合、外側のループが n 回、内側のループも n 回実行されるため、合計で n × n、つまり n² 回の処理が行われることになる。データの数が少し増えるだけでも、処理時間は劇的に増加してしまうため、大規模なデータには不向きである。

さらに効率が悪いのが「O(2ⁿ) 指数時間」だ。これは、入力データ量 n がわずかに増えるだけで、処理時間が爆発的に増加する。例としては、ある集合からすべての可能な部分集合を生成するような処理がある。各要素について「含めるか、含めないか」の2つの選択肢があるため、要素が n 個あると 2 の n 乗（2ⁿ）のパターンが生まれることになる。このようなアルゴリズムは、n の値が小さい場合しか実用的ではない。

そして、最も効率が悪いとされるのが「O(n!) 階乗時間」だ。これは、入力データ量 n の階乗（n! = n × (n-1) × ... × 1）に比例して処理時間が増えることを意味する。例えば、異なる n 個の要素のすべての可能な並び順（順列）を生成するような処理がこれに当たる。n が少しでも大きくなると、処理時間は天文学的な値になり、現実的な時間では計算が終わらないため、実用性は極めて低い。

Big O記法を理解する上で重要なポイントがいくつかある。まず、「定数を無視する」というルールだ。例えば、処理が5nステップかかる場合でも、Big O記法ではO(n)と表現する。また、「下位の項を無視する」というルールも存在する。もし処理時間がn² + nステップかかる場合、nが大きくなるとn²の方が支配的になるため、O(n²)と表現する。さらに、対数の底（例えばlog₂ nやlog₁₀ n）はBig O記法においては重要ではなく、すべてO(log n)として扱われる。異なる処理の効率を合算する場合は、最も支配的な（大きい）Big Oの項を採用する。これらの基本的な考え方を身につけることで、プログラムの効率を正しく評価し、より良いシステムを設計できるようになるだろう。