アルゴリズムとは？基本の考え方をやさしく解説

アルゴリズムとは「問題を解くための手順」のことです。料理のレシピが「材料から料理を作る手順」であるように、アルゴリズムは「入力データから目的の結果を得る手順」を指します。この記事では、アルゴリズムの基本的な考え方と代表的な種類を、身近な例とコードで解説します。

アルゴリズムとは何か

アルゴリズムは、コンピュータサイエンスの用語に見えますが、実は日常生活にもあふれています。ある問題を解決するための「明確で有限な手順」がアルゴリズムです。

日常の中のアルゴリズム

たとえば「辞書で単語を引く」という行為には、アルゴリズムが使われています。

辞書のだいたい真ん中あたりを開く
目的の単語が今のページより前にあるか後にあるか判断する
前にあれば前半を、後にあれば後半を同じ方法で探す
目的の単語が見つかるまで繰り返す

この「真ん中で分けて絞り込む」方法は「二分探索」と呼ばれるアルゴリズムそのものです。

良いアルゴリズムとは

同じ問題を解くにも、効率の良い方法と悪い方法があります。辞書で単語を探すとき、1ページ目から順番にめくっていく方法でも見つかりますが、時間がかかります。二分探索のほうがはるかに速いことは直感的にもわかるでしょう。

良いアルゴリズムの条件は主に次の3つです。

正しい結果が得られること
効率が良いこと（速い、メモリを使いすぎない）
手順が明確で再現できること

ソートアルゴリズム

ソート（並べ替え）は、アルゴリズムの中でも最も基本的なものの1つです。データを昇順や降順に並べ替える処理で、さまざまな方法があります。

バブルソート

最もシンプルなソートアルゴリズムです。隣り合う2つの要素を比較し、順番が逆なら入れ替えることを繰り返します。

def bubble_sort(arr):
    n = len(arr)
    for i in range(n):
        for j in range(0, n - i - 1):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
    return arr

numbers = [64, 34, 25, 12, 22, 11, 90]
print(bubble_sort(numbers))
# [11, 12, 22, 25, 34, 64, 90]

バブルソートは理解しやすいものの、データ量が増えると極端に遅くなります。

もっと速いソート

実用的なソートアルゴリズムには、クイックソートやマージソートがあります。Pythonの sorted() 関数は「Timsort」というアルゴリズムを使っており、さまざまなデータパターンに対して効率よく動作します。

numbers = [64, 34, 25, 12, 22, 11, 90]

# Pythonの組み込みソート（Timsort）
sorted_numbers = sorted(numbers)
print(sorted_numbers)
# [11, 12, 22, 25, 34, 64, 90]

実務ではプログラミング言語に用意されたソート関数を使うのが一般的です。ソートアルゴリズムを自分で実装する必要はほとんどありませんが、仕組みを理解しておくとパフォーマンスの判断に役立ちます。

探索アルゴリズム

探索とは、データの中から目的の値を見つけ出す処理です。ここでは代表的な2つの方法を紹介します。

線形探索（リニアサーチ）

先頭から順番に1つずつ調べていく方法です。データが整列されていなくても使えますが、データ量が多いと時間がかかります。

def linear_search(arr, target):
    for i, value in enumerate(arr):
        if value == target:
            return i  # 見つかった位置を返す
    return -1  # 見つからなかった

data = [3, 7, 1, 9, 4, 6, 2]
print(linear_search(data, 9))   # 3（インデックス3に存在）
print(linear_search(data, 5))   # -1（見つからない）

二分探索（バイナリサーチ）

データがあらかじめ昇順に並んでいる場合に使える、高速な探索方法です。先ほどの辞書の例と同じ考え方です。

def binary_search(arr, target):
    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

data = [1, 3, 5, 7, 9, 11, 13, 15]
print(binary_search(data, 7))   # 3
print(binary_search(data, 6))   # -1

二分探索は1回の比較でデータの半分を除外できるため、データ量が増えても高速に動作します。

2つの探索方法の比較

100万件のデータから1つの値を探す場合を考えてみましょう。

線形探索: 最悪で100万回の比較が必要
二分探索: 最悪でも約20回の比較で見つかる

この圧倒的な差が、アルゴリズムの選択がなぜ重要なのかを物語っています。

計算量という考え方

アルゴリズムの効率を評価するために「計算量」という指標があります。データ量が増えたときに、処理時間がどのように増えるかを表します。

O記法（ビッグオー記法）

計算量は「O記法」で表すのが一般的です。O(n) は「データ数nに比例して時間がかかる」という意味です。

代表的な計算量を遅い順に並べると、次のようになります。

O(1): データ量に関係なく一定時間（配列のインデックスアクセスなど）
O(log n): データが倍になっても1回増える程度（二分探索）
O(n): データ量に比例（線形探索）
O(n log n): 効率的なソート（クイックソート、マージソートなど）
O(n^2): データ量の2乗に比例（バブルソート）

具体的な処理時間のイメージ

n = 1,000,000（100万）のとき、各計算量の処理回数を概算すると次のようになります。

O(1): 1回
O(log n): 約20回
O(n): 100万回
O(n log n): 約2,000万回
O(n^2): 1兆回

O(n^2) のアルゴリズムでは、データが100万件あると実用的な時間で処理が終わりません。大量のデータを扱うプログラムでは、計算量を意識することが重要です。

Pythonで処理時間を比べてみる

import time

# データの準備
data = list(range(1000000))
target = 999999

# 線形探索の時間計測
start = time.time()
for i, v in enumerate(data):
    if v == target:
        break
linear_time = time.time() - start

# 二分探索の時間計測
start = time.time()
left, right = 0, len(data) - 1
while left <= right:
    mid = (left + right) // 2
    if data[mid] == target:
        break
    elif data[mid] < target:
        left = mid + 1
    else:
        right = mid - 1
binary_time = time.time() - start

print(f"線形探索: {linear_time:.6f}秒")
print(f"二分探索: {binary_time:.6f}秒")

実行すると、二分探索が圧倒的に速いことを数値で確認できます。

アルゴリズムの身近な活用例

アルゴリズムは、ふだん使っているサービスの裏側で活躍しています。

検索エンジン

検索エンジンは膨大なWebページの中から、入力したキーワードに関連するページを瞬時に見つけ出します。これにはインデックス構造や文書のランキングアルゴリズムが使われています。

経路探索

地図アプリのナビゲーションでは「最短経路アルゴリズム」が使われています。出発地から目的地までの経路は無数にありますが、その中から最も早い経路を効率的に見つけ出しています。

レコメンデーション

動画配信サービスやECサイトの「おすすめ」機能にもアルゴリズムが使われています。ユーザーの行動履歴や似た嗜好を持つ他のユーザーのデータをもとに、興味を持ちそうなコンテンツを推定しています。

アルゴリズムを学ぶ意義

アルゴリズムの知識は、直接コードを書くとき以外にも役立ちます。

プログラミングの基礎体力になる

アルゴリズムの考え方を身につけると、「どうすれば効率よく処理できるか」を自然に考えられるようになります。これはどの言語やフレームワークを使う場合にも共通する基礎的な能力です。

問題解決能力が高まる

アルゴリズムの学習は「大きな問題を小さな問題に分解する」「パターンを見つける」といった思考力を養います。これはプログラミングに限らず、さまざまな場面で応用できます。

まとめ

この記事では、アルゴリズムの基本を解説しました。

アルゴリズムは「問題を解くための明確な手順」
ソートや探索は代表的なアルゴリズム
同じ問題でもアルゴリズムの選択で処理速度が大きく変わる
計算量（O記法）でアルゴリズムの効率を評価できる
検索エンジンやナビゲーションなど、身近なサービスの裏で活躍している

アルゴリズムの理解は、より効率的なプログラムを書くための基盤となります。まずはこの記事で紹介したソートや探索のコードを動かして、処理速度の違いを実感してみてください。