Zenn
🐍

Python アルゴリズム学習 Day 3：線形探索アルゴリズムの計算量分析（実践編）

に公開
Python
Python 3
アルゴリズム
tech

はじめに

前回の記事では「Big O 記法の基礎」として、アルゴリズムの効率性を評価するための理論的な概念について学習しました。今回は「線形探索アルゴリズムの計算量分析」として、理論だけでなく実際に手を動かして計算量を測定し、理解を深めていきます。

本記事の完全なソースコードはgithub リポジトリを参照してください。

線形探索アルゴリズムの計算量とは

線形探索は、配列の先頭から順番に要素を調べていき、目的の値を探すシンプルなアルゴリズムです。その計算量は以下のように特徴づけられます：

  1. 最良のケース (Best Case)

    • 目的の要素が配列の先頭にある場合
    • 比較回数: 1 回
    • 計算量: O(1)

  2. 平均的なケース (Average Case)

    • 目的の要素が配列内のランダムな位置にある場合
    • 平均比較回数: n/2 回
    • 計算量: O(n/2) ≈ O(n)

  3. 最悪のケース (Worst Case)

    • 目的の要素が配列の末尾にある場合、または存在しない場合
    • 比較回数: n 回
    • 計算量: O(n)

  4. 空間計算量 (Space Complexity)

    • 追加のメモリ使用がほとんどない
    • 計算量: O(1)

実装による検証

今回、これらの理論的な計算量を実際に検証するために、linear_search_analysis.pyというコードを実装しました。このコードでは、線形探索の比較回数と実行時間を実際に測定し、様々なケースでの挙動を観察します。

線形探索の実装

まず、比較回数をカウントする機能を追加した線形探索関数を実装しました：

def linear_search(arr, target):
    """
    線形探索アルゴリズム

    Parameters:
        arr (list): 探索対象の配列
        target: 探索する値

    Returns:
        int: 見つかった場合はそのインデックス、見つからなかった場合は-1
        int: 比較回数
    """
    # 比較回数を数えるカウンター
    comparisons = 0

    # 配列の先頭から順に探索
    for i in range(len(arr)):
        # 比較回数をカウントアップ
        comparisons += 1

        # 現在の要素が探索対象と一致するか確認
        if arr[i] == target:
            # 一致したら、インデックスと比較回数を返す
            return i, comparisons

    # 見つからなかった場合、-1と比較回数を返す
    return -1, comparisons

様々なケースでのテスト

次に、この線形探索関数を使って、様々なケースでの動作を確認する関数を実装しました：

  1. 最良のケース：配列の先頭要素を探す
  2. 平均的なケース：配列の中間付近の要素を探す
  3. 最悪のケース：配列の末尾要素を探す
  4. 要素が存在しない場合：配列内に存在しない値を探す

また、配列サイズが計算量にどのように影響するかも検証するため、異なるサイズの配列（10, 100, 1000, 10000）で比較回数を測定しました。

実行結果と考察

これらの結果は、GitHub リポジトリ上のファイル linear_search_analysis.py をご自身の環境で実行することで、実際にご確認いただけます。

最良のケース（先頭要素）

小さな配列（サイズ 10）での実行結果：

配列: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
探索値: 0 (先頭の要素)
結果: インデックス 0 で見つかりました
比較回数: 1 回
実行時間: 0.00000048 秒

予想通り、比較回数は 1 回でした。配列のサイズが大きくなっても、この最良ケースでの比較回数は常に 1 回です。これは O(1)の時間計算量を持つことを示しています。

平均的なケース（中間要素）

配列サイズ: 100
  平均的なケース（中間）: 50 回の比較

配列サイズ: 1000
  平均的なケース（中間）: 500 回の比較

配列サイズ n に対して、平均的なケースの比較回数は約 n/2 になることがわかります。これは O(n)の時間計算量を持つことを示しています。

最悪のケース（末尾要素）

配列サイズ: 100
  最悪のケース（末尾）: 100 回の比較

配列サイズ: 1000
  最悪のケース（末尾）: 1000 回の比較

最悪のケースでは、配列内のすべての要素を調べる必要があるため、比較回数は配列サイズ n と等しくなります。これも O(n)の時間計算量を示しています。

要素が存在しない場合

配列サイズ: 100
  存在しない要素: 100 回の比較

配列サイズ: 1000
  存在しない要素: 1000 回の比較

要素が存在しない場合も、すべての要素を調べる必要があるため、最悪のケースと同様に比較回数は配列サイズ n と等しくなります。

入力サイズの影響

測定結果から、線形探索の比較回数は以下のような傾向を持つことがわかりました：

サイズ 最良のケース 平均的なケース 最悪のケース
10 1 5 10
100 1 50 100
1000 1 500 1000
10000 1 5000 10000

この結果から、線形探索の比較回数は理論通りに：

  • 最良のケース：常に 1 回（O(1)）
  • 平均的なケース：n/2 回（O(n)）
  • 最悪のケース：n 回（O(n)）

となることが実証されました。

実用上の考慮点

実験結果から、以下のような考察ができます：

  1. 小さな配列では効率的：
    配列のサイズが小さい場合、線形探索は十分に高速です。例えば、サイズ 10 や 100 の配列では、最悪のケースでも比較回数は少なく、実行時間も非常に短いです。

  2. 大きな配列では非効率的：
    配列のサイズが大きくなるほど、最悪のケースと平均的なケースでの比較回数が顕著に増加します。サイズ 10000 の配列では、最悪のケースで 10000 回の比較が必要になります。

  3. ソート済み配列ではより効率的な方法がある：
    配列がソート済みの場合、二分探索のようなより効率的なアルゴリズム（O(log n)）を使用することで、検索効率を大幅に向上させることができます。

まとめ

今回は、線形探索アルゴリズムの計算量を実際に測定し、理論的な計算量と実測値が一致することを確認しました。最良のケース、平均的なケース、最悪のケースでの比較回数と実行時間を観察することで、Big O 記法の意味をより具体的に理解することができました。

線形探索は実装が非常にシンプルなアルゴリズムですが、大きなデータセットでは効率が悪くなる可能性があります。適切なシチュエーションでの使用や、必要に応じてより効率的なアルゴリズムを選択することの重要性も学びました。

Discussion