線形探索: データを一つ一つ辿る探索アルゴリズムの基礎
はじめに
昨年、競技プログラミングを始めて、早々に挫折しましたが、1年振りにやる気が戻ってきました。
今回は、2024年末までに、AtCoderのレーティングで緑（全体の上位30％ぐらい）を目標に学習を進めたいと思います。
AtCoder https://atcoder.jp/home
レーティング緑を達成するためには、基礎的なアルゴリズムは習得する必要があります。
その中でも、線形探索はシンプルかつ理解しやすいアルゴリズムであり、競技プログラミングの入門者にとって、取り掛かりやすい内容です。
線形詮索とは
線形探索は、データの集合から目的のデータを探し出す手法の一つです。リストや配列などのデータ構造において、先頭から順番に要素を調べ、目的の要素が見つかるまで続けるという基本的な原則に基づいたアルゴリズムです。
以下のような問題を線形探索で解決することができます。
- 未ソートのデータの中から最小値を見つける問題
- 文字列内で特定の文字を探す問題
具体的な実装例を確認していきましょう。
アルゴリズムの実装
以下は、Pythonを用いた線形探索の実装例です。
1.未ソートのデータの中から最小値を見つける問題:
- 問題: 未ソートの整数のリストが与えられたとき、最小の値を見つけるプログラムを作成してください。
- 解決方法: 線形探索を使用して、リストを先頭から順番に探索し、最小値を見つけます。リストをイテレートして各要素と比較し、より小さい値が見つかれば、最小値を更新します。
def find_minimum_value(nums):
if not nums: # リストが空の場合
return None
min_value = nums[0] # 最小値を仮にリストの最初の要素に設定
for num in nums:
if num < min_value:
min_value = num
return min_value2.文字列内で特定の文字を探す問題
- 問題: 与えられた文字列に含まれる特定の文字の数を数えるプログラムを作成してください。
- 解決方法: 線形探索を使用して、リストを先頭から順番に探索し、特定の文字が見つかった場合、カウントを増やしていきます。
def count_characters(input_string, target_character):
# カウンターの初期値を設定
count = 0
# 入力文字列を1文字ずつ見ていくループ
for char in input_string:
# もし現在見ている文字が目標の文字と一致していれば
if char == target_character:
# カウンターを1増やす
count += 1
# 最終的なカウントを返す
return count線形詮索のメリット・デメリット
利点
- 実装がシンプルで理解しやすい。
- データセットが小さい場合、高速に動作する。
欠点
- データセットが大きい場合、探索に時間がかかる。
- 最悪の場合、全ての要素を探索する必要があるため、時間計算量はO(n)となる。
※O(n)は「オーダー・オブ・n」と読み、線形時間と呼ばれるものです。入力サイズnに比例して実行時間が増加すること。
まとめ
線形探索は基本的ながらも実用的な探索アルゴリズムです。初心者にとっては理解しやすく、小さなデータセットでは十分に高効率のようです。AtCoderのBeginner Contestの1.2問目の問題は線形詮索で回答できることが多いイメージがあります。
しかし、大規模なデータセットでは他の探索アルゴリズムが適していることがあります。大規模なデータを扱う問題で、線形詮索を利用して実装すると、TLE (Time Limit Exceeded)で不正解となることが多いです。問題の内容に応じて、アルゴリズムを使い分けれるように他のアルゴリズムの学習もしなければいけません。
