<一覧に戻る
探索アルゴリズムの時間計算量の基礎
探索アルゴリズムは、データ構造の中から特定の値を見つけ出すための手法です。プログラミングやアルゴリズムの学習において、探索アルゴリズムの理解は非常に重要です。この教材では、探索アルゴリズムの時間計算量に焦点を当て、基本的な線形探索と二分探索の実装を行い、それぞれの計算量について解説します。
1. 線形探索の計算量: O(n)
線形探索は、リストや配列の全ての要素を順番に確認しながら、目的の要素が存在するかどうかを探す方法です。
- 手順: 配列の先頭から順番に1つずつ要素を確認し、目的の値と一致する要素が見つかるまで比較を繰り返します。
- 最悪の場合: 配列の最後まで確認しても見つからないとき、全ての要素を調べることになります。配列の長さを ( n ) とすると、最悪で ( n ) 回の比較が必要になります。
- 計算量: 線形探索では、要素数に比例して探索時間が増加するため、時間計算量は O(n) です。
線形探索の例
# 配列内でターゲット値を探す
arr = [1, 3, 5, 7, 9]
target = 9
for i in range(len(arr)):
if arr[i] == target:
print(f"Found at index {i}")
break
このコードでは、最悪でリストの最後まで探索することになります。
2. 二分探索の計算量: O(log n)
二分探索は、ソートされたリストや配列に対して使用できるアルゴリズムで、中央から範囲を半分に分割して探索します。
- 手順: まず配列の中央の要素を確認し、それがターゲットと一致するか確認します。
- 中央の要素がターゲットより大きい場合、探索範囲を中央より左側に限定します。
- 中央の要素がターゲットより小さい場合、探索範囲を中央より右側に限定します。
- 最悪の場合: このプロセスを繰り返すことで、探索範囲が半分ずつ減っていきます。最終的に探索範囲が1つになるまで、計算量は (\log_2 n) に収束します。
- 計算量: 二分探索では、探索範囲が毎回半分になるため、時間計算量は O(log n) になります。
二分探索の例
def binary_search(arr, target):
left, right = 0, len(arr) - 1
while left <= right:
mid = left + (right - left) // 2
if arr[mid] == target:
return mid
elif arr[mid] < target:
left = mid + 1
else:
right = mid - 1
return -1
arr = [1, 3, 5, 7, 9]
target = 9
print(binary_search(arr, target)) # 出力は 4（インデックス）
このコードでは、中央の要素に対する比較のみを行い、範囲を半分ずつ減らしていきます。
計算量の違いの具体的な影響
-
小さなデータサイズ: ( n ) が小さい場合、線形探索でも二分探索でもそこまで大きな違いが生まれません。しかし、データが増えると違いが顕著になります。
-
大きなデータサイズ:
- たとえば、データサイズ ( n = 1,000,000 ) の場合:
- 線形探索 (O(n)) では、最悪の場合 1,000,000 回の比較が必要です。
- 二分探索 (O(log n)) では、最悪でも 約20回の比較で済みます。
-
実際のパフォーマンス:
- 線形探索では、データが増えると比例して処理時間も増加します。
- 二分探索では、データ量が大きくなっても増加速度が緩やかであるため、特に大規模データでは圧倒的に効率的です。
まとめ
- 線形探索: 比較回数がデータサイズに比例して増えるため、O(n)の計算量。
- 二分探索: データを半分ずつ絞り込むため、O(log n)の計算量で効率的。
大規模なソート済みデータを扱う場合には、二分探索が特に有効なアルゴリズムになります。