【初心者向け】O記法（ビッグオー記法）とは？O(1)、O(n)、O(n²)をわかりやすく解説
テックジム東京本校では、情報科目の受験対策指導もご用意しております。
目次
O記法（オーダー記法）とは
O記法（ビッグオー記法、Big O notation）は、アルゴリズムの**計算量（処理時間やメモリ使用量）**を表現するための数学的記法です。プログラムが「どれくらい速く動くか」「データ量が増えたときにどれくらい遅くなるか」を評価する際に使用されます。
アルゴリズムを選ぶ際や、コードの最適化を行う際に、O記法を理解していることは非常に重要です。
なぜO記法が必要なのか
- パフォーマンスの予測: データ量が増えたときの処理時間を予測できる
- アルゴリズムの比較: 複数のアルゴリズムを客観的に比較できる
- ボトルネックの特定: プログラムの遅い部分を見つけやすくなる
O記法の基本的な読み方
O記法は「O(何か)」という形で表現されます。括弧内の値が、データ量（通常はnで表現）に対する計算量の増加率を示します。
基本的な考え方:
- n: データの個数やサイズ
- O(f(n)): データ量nに対する計算量の増加傾向
主要なO記法一覧（速い順）
1. O(1) – 定数時間
特徴: データ量に関係なく、常に一定の時間で処理が完了します。
具体例:
- 配列の特定位置へのアクセス
- ハッシュテーブルでの検索（理想的な場合）
- スタックのpush/pop操作
# O(1)の例：配列の要素へのアクセス
def get_first_element(array):
return array[0] # データ量に関係なく即座に取得
グラフのイメージ: 横ばいの直線（どんなにデータが増えても処理時間は変わらない）
2. O(log n) – 対数時間
特徴: データ量が増えても、処理時間の増加は非常に緩やか。データ量が2倍になっても、処理時間はほんの少ししか増えません。
具体例:
- 二分探索
- バランスされた二分探索木での検索
# O(log n)の例：二分探索
def binary_search(sorted_array, target):
left, right = 0, len(sorted_array) - 1
while left <= right:
mid = (left + right) // 2
if sorted_array[mid] == target:
return mid
elif sorted_array[mid] < target:
left = mid + 1
else:
right = mid - 1
return -1
実際の数値例:
- n=1000の場合: 約10回の操作
- n=1000000の場合: 約20回の操作
3. O(n) – 線形時間
特徴: データ量に比例して処理時間が増加します。データが2倍になれば、処理時間も2倍になります。
具体例:
- 配列の全要素を走査
- リストの中から特定の値を探す（線形探索）
- 配列の要素の合計を計算
# O(n)の例：配列内の最大値を探す
def find_max(array):
max_value = array[0]
for num in array: # n回のループ
if num > max_value:
max_value = num
return max_value
実際の数値例:
- n=1000の場合: 約1000回の操作
- n=1000000の場合: 約1000000回の操作
4. O(n log n) – 線形対数時間
特徴: O(n)とO(log n)を組み合わせた計算量。効率的なソートアルゴリズムの多くがこの計算量です。
具体例:
- マージソート
- クイックソート（平均的な場合）
- ヒープソート
# O(n log n)の例：マージソート
def merge_sort(array):
if len(array) <= 1:
return array
mid = len(array) // 2
left = merge_sort(array[:mid]) # log n回の分割
right = merge_sort(array[mid:])
return merge(left, right) # n回の操作でマージ
5. O(n²) – 二乗時間
特徴: データ量の2乗に比例して処理時間が増加します。データが2倍になると、処理時間は4倍になります。
具体例:
- バブルソート
- 選択ソート
- 挿入ソート
- 二重ループでの全組み合わせチェック
# O(n²)の例：バブルソート
def bubble_sort(array):
n = len(array)
for i in range(n): # 外側のループ: n回
for j in range(n - 1): # 内側のループ: n回
if array[j] > array[j + 1]:
array[j], array[j + 1] = array[j + 1], array[j]
return array
実際の数値例:
- n=100の場合: 約10000回の操作
- n=1000の場合: 約1000000回の操作（100倍のデータで100倍の計算量）
6. O(2ⁿ) – 指数時間
特徴: データ量が1増えるだけで処理時間が2倍になる、非常に遅いアルゴリズム。実用的には使えないことが多いです。
具体例:
- フィボナッチ数列の素朴な再帰実装
- べき集合の生成
# O(2ⁿ)の例：フィボナッチ数（非効率な実装）
def fibonacci(n):
if n <= 1:
return n
return fibonacci(n - 1) + fibonacci(n - 2) # 毎回2つに分岐
実際の数値例:
- n=10の場合: 約1024回の操作
- n=20の場合: 約1048576回の操作
- n=30の場合: 約10億回の操作
O記法の計算量比較表
データ量が増えたときの計算量の増加を比較してみましょう。
| データ量(n) | O(1) | O(log n) | O(n) | O(n log n) | O(n²) | O(2ⁿ) |
|---|---|---|---|---|---|---|
| 10 | 1 | 3 | 10 | 30 | 100 | 1024 |
| 100 | 1 | 7 | 100 | 700 | 10000 | 1.27×10³⁰ |
| 1000 | 1 | 10 | 1000 | 10000 | 1000000 | – |
この表から、O(n²)以上の計算量は大規模データには不向きであることがわかります。
O記法を使った実践的なアルゴリズム選択
検索アルゴリズムの選択
状況: 1000個のデータから特定の値を探したい
| アルゴリズム | 計算量 | データの前提条件 | 平均操作回数 |
|---|---|---|---|
| 線形探索 | O(n) | なし | 500回 |
| 二分探索 | O(log n) | ソート済み | 10回 |
| ハッシュテーブル | O(1) | 事前にハッシュテーブル構築 | 1回 |
結論: データがソート済みなら二分探索、頻繁に検索するならハッシュテーブルを使うのが効率的です。
ソートアルゴリズムの選択
状況: 10000個のデータをソートしたい
| アルゴリズム | 計算量 | 特徴 | おすすめ度 |
|---|---|---|---|
| バブルソート | O(n²) | シンプルだが遅い | ✗ |
| マージソート | O(n log n) | 安定で高速 | ✓ |
| クイックソート | O(n log n) | 平均的に最速 | ✓ |
O記法を理解する上での重要なポイント
1. 定数項は無視する
O記法では、定数倍の差は無視されます。
× O(2n) → ○ O(n)
× O(n/2) → ○ O(n)
× O(100) → ○ O(1)
理由: データ量が十分大きくなれば、定数倍の差は誤差範囲になるため。
2. 最も大きい項だけを残す
複数の項がある場合、最も影響の大きい項だけを残します。
× O(n² + n + 100) → ○ O(n²)
× O(n log n + n) → ○ O(n log n)
× O(2ⁿ + n²) → ○ O(2ⁿ)
3. 最悪ケースを基準にする
O記法は通常、最悪の場合の計算量を表します。
例: クイックソートは平均O(n log n)ですが、最悪ケースではO(n²)になります。
よくある質問（FAQ）
Q1: O(n)とO(2n)は違うの?
A: O記法では同じです。定数倍は無視されるため、どちらも**O(n)**と表記します。
Q2: 空間計算量とは?
A: 時間計算量がアルゴリズムの処理速度を表すのに対し、空間計算量はメモリ使用量を表します。これもO記法で表現できます。
Q3: O(log n)のlogの底は?
A: 通常は底が2ですが、O記法では底が何であっても計算量のオーダーは変わらないため、あまり気にする必要はありません。
まとめ
O記法（ビッグオー記法）は、アルゴリズムの効率性を評価する重要な指標です。
覚えておくべきポイント:
- O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2ⁿ) の順に遅くなる
- データ量が大きい場合、O(n²)以上は避けるべき
- 定数項は無視し、最も大きい項だけを考える
- アルゴリズム選択の際は、データの性質と計算量の両方を考慮する
プログラミングの実践において、O記法を意識することで、より効率的なコードを書けるようになります。特に大規模データを扱う際には、計算量の違いがパフォーマンスに大きく影響するため、適切なアルゴリズムを選択することが重要です。
関連キーワード: 計算量、時間計算量、空間計算量、アルゴリズム、データ構造、ビッグオー、オーダー記法、パフォーマンス最適化、プログラミング効率化
■らくらくPython塾 – 読むだけでマスター
【現役エンジニア歓迎】プログラミング学習お悩み相談会
【情報I】受験対策・お悩み相談会（オンライン・無料）
【オンライン無料】ゼロから始めるPython爆速講座
■テックジム東京本校
格安のプログラミングスクールといえば「テックジム」。
講義動画なし、教科書なし。「進捗管理とコーチング」で効率学習。
対面型でより早くスキル獲得、月額2万円のプログラミングスクールです。
情報科目の受験対策指導もご用意しております。
