🐍
Python アルゴリズム学習 Day 2：Big O 記法の基礎

2025/04/22に公開
 はじめにアルゴリズムを学ぶ上で重要なのは、そのアルゴリズムがどれだけ効率的に動作するかを理解することです。アルゴリズムの効率性を評価する方法として「Big O 記法（ビッグオー記法）」があります。今回は、この記法の基本について、実際のコード例と共に学んでいきます。
本記事の完全なソースコードはgithub リポジトリを参照してください。

 Big O 記法とは？Big O 記法は、アルゴリズムの実行時間や必要なメモリ量が入力サイズによってどのように変化するかを表す方法です。簡単に言えば、「入力が大きくなったとき、どれだけの時間やメモリが必要になるか」という「増加率」を表現します。
例えば、100 個のデータを処理するのに 1 秒かかるアルゴリズムがあるとして、1 万個のデータを処理する場合はどうなるでしょうか？アルゴリズムによって大きく変わります：
一部のアルゴリズムは 2 秒で済む（良い！）
一部のアルゴリズムは 100 秒かかる（まあまあ）
一部のアルゴリズムは 10000 秒かかる（悪い！）
Big O 記法はこの違いを数学的に表現します。

 主な Big O 記法の種類以下に代表的な Big O 記法の種類と、それぞれの特徴を示します。

 O(1) - 定数時間入力サイズに関係なく、常に同じ時間で実行されるアルゴリズムです。
def constant_time_example(arr):
    """O(1) - 定数時間の例"""
    return arr[0] if arr else None
このコードは、配列の先頭要素にアクセスしているだけなので、配列のサイズに関わらず常に同じ時間で実行されます。

 O(log n) - 対数時間入力サイズの対数に比例する時間で実行されるアルゴリズムです。二分探索がその代表例です。
def logarithmic_time_example(arr, target):
    """O(log n) - 対数時間の例（二分探索）"""
    # ソート済みの配列を前提とする
    left, right = 0, len(arr) - 1

    while left <= right:
        mid = (left + right) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1

    return -1
二分探索では、各ステップで探索範囲が半分になるため、非常に効率的です。

 O(n) - 線形時間入力サイズに比例する時間で実行されるアルゴリズムです。
def linear_time_example(arr):
    """O(n) - 線形時間の例"""
    total = 0
    for item in arr:
        total += item
    return total
このコードは配列の各要素に一度だけアクセスするため、配列のサイズに比例した時間がかかります。

 O(n²) - 二次時間入力サイズの二乗に比例する時間で実行されるアルゴリズムです。
def quadratic_time_example(arr):
    """O(n²) - 二次時間の例"""
    n = len(arr)
    result = []
    for i in range(n):
        for j in range(n):
            result.append(arr[i] * arr[j])
    return result
このコードは二重ループを使用しており、配列のサイズが大きくなると急速に実行時間が増加します。

 実行時間の比較サンプルの実行関数を使用して、各計算量の違いを実際に測定してみました。以下が実行結果の例です：
O(1) - サイズ 100: 0.000000 秒
O(n) - サイズ 100: 0.000003 秒
O(log n) - サイズ 100: 0.000002 秒
O(1) - サイズ 1000: 0.000001 秒
O(n) - サイズ 1000: 0.000019 秒
O(log n) - サイズ 1000: 0.000002 秒
O(1) - サイズ 10000: 0.000000 秒
O(n) - サイズ 10000: 0.000193 秒
O(log n) - サイズ 10000: 0.000002 秒
O(1) - サイズ 100000: 0.000000 秒
O(n) - サイズ 100000: 0.001912 秒
O(log n) - サイズ 100000: 0.000003 秒

O(n²)の計算量の測定:
O(n²) - サイズ 10: 0.000008 秒
O(n²) - サイズ 50: 0.000156 秒
O(n²) - サイズ 100: 0.000525 秒
O(n²) - サイズ 500: 0.013743 秒
この実験の結果、以下のことが分かりました：

O(1): 入力サイズが増加しても実行時間はほぼ一定

O(log n): 入力サイズが大きく増加しても実行時間は緩やかにしか増加しない

O(n): 入力サイズに比例して実行時間が増加する

O(n²): 入力サイズの二乗に比例して実行時間が急激に増加する（例：サイズが 10 倍になると実行時間は約 100 倍）

 二分探索（O(log n)）の詳細対数時間の代表例である二分探索をより深く理解するために、各ステップでの処理を視覚化するサンプルコードも作成しました。サンプルを実行して、例えば、小さな配列で 7 という値を探す過程は以下のようになります：
探索対象配列: [1, 3, 5, 7, 9, 11, 13, 15]
探索値: 7

ステップ 1:
配列:  1  <3> <5> [7] <9> <11> <13> <15>
探索範囲: left=0 (値=1), right=7 (値=15)
中央: mid=3 (値=7)
一致! arr[3] == 7
このように、二分探索は一回のステップで正しい位置を見つけることができました（この例ではたまたま最初の中央値が探索値と一致）。大きな配列でも、ステップ数は対数関数的にしか増加しないため、非常に効率的です。

 計算量の重要性計算量は、特に大きなデータセットを扱う場合に重要な意味を持ちます。例えば、100 万個の要素を持つ配列では：
O(1) のアルゴリズム: ほぼ一瞬で完了
O(log n) のアルゴリズム: 約 20 ステップで完了（log₂(1,000,000) ≈ 20）
O(n) のアルゴリズム: 100 万ステップ必要
O(n²) のアルゴリズム: 1 兆ステップ必要（現実的には計算不可能）
このように、アルゴリズムの計算量はプログラムの実行可能性や効率性に大きく影響します。そのため、問題に応じて適切な計算量を持つアルゴリズムを選択することが重要です。

 まとめBig O 記法は、アルゴリズムの効率性を評価するための重要な指標です。主な計算量には、O(1)、O(log n)、O(n)、O(n²)などがあり、それぞれ異なる増加率を持ちます。アルゴリズムを選択する際は、この計算量を考慮することで、より効率的なプログラムを作成することができます。
はじめに

Big O 記法とは？

主な Big O 記法の種類

O(1) - 定数時間

O(log n) - 対数時間

O(n) - 線形時間

O(n²) - 二次時間

実行時間の比較

二分探索（O(log n)）の詳細

計算量の重要性

まとめ

Discussion
