アルゴリズム基礎とは？整列・探索・再帰をやさしく解説

「アルゴリズムって、何のために学ぶの?」
「整列・探索・再帰って、どう違うの?」
「Big O 記法って、何を意味してるの?」

そんな疑問を抱える、基本情報技術者の科目B 対策を始めたあなたへ。

結論から言えば、
アルゴリズムとは、問題を解くための「手順の設計図」のことです。整列・探索・再帰の3つを押さえると、科目B の出題の見通しが立ちます
と説明されるのが一般的です。

「アルゴリズム」とは、決まった結果に到達するための手順のセットを指す言葉とされています。手順の「速さ」を表す指標が計算量(Big O)です。

この記事では、整列(バブル・クイック・マージ)、探索(線形・二分)、再帰と Big O までを、初心者のあなた向けにメタファーでやさしくまとめました。基本情報技術者の科目B 対策にも役立ちます。

1. アルゴリズムとは — 料理レシピの手順設計

あなたが「アルゴリズム」という言葉に出会ったとき、まず押さえたいのは「問題を解くための手順の設計図」という基本定義です。

同じ目的を達成する手順は、いくつも考えられます。たとえば「100人の名簿を名前順に並べる」という目的に対しても、隣同士を比べていく方法、基準値で分割する方法、いったん分けてから統合する方法などが存在します。

ここでイメージしてほしいのが、料理のレシピです。同じカレーを作る場合でも、材料を切ってから煮込むのか、煮込みながら切るのかで、出来上がりまでの時間と手間が変わります。アルゴリズムも同じで、同じ結果に至る手順でも、設計次第で速さと正確さが変わる仕組みと言われています。

アルゴリズムの良し悪しは、「正確さ」と「速さ(計算量)」の2つで評価されるのが一般的とされています。基本情報技術者の科目B では、手順を読み取って動作を追う問題が中心になります。

あなたが最初に出会う代表的なアルゴリズムが、整列(ソート)です。バラバラのデータを、ある順序で並び替える手順を指す言葉とされています。試験で問われるのは主に3種類です。

3種類の違いは、計算量に表れます。バブルソートは平均で O(n²)、クイックソートとマージソートは平均で O(n log n) と言われています。データが多いほど、後者の方が速くなるのが一般的です。

別の観点として、整列は「データの並びがその後の処理を速くする」場面で使われると言われています。たとえば後で説明する二分探索は、整列されたデータに対してしか使えない手順です。整列と探索は組み合わせで効いてくると整理しておくと分かりやすいです。

→ 整列されたデータを大規模に管理する仕組みとしては、データベースとはも合わせて押さえると、整列が実務で使われる場面のイメージが広がります。

あなたがデータの中から目的の値を見つける手順が、探索(サーチ)です。代表的な手順は2種類で、考え方が大きく異なる仕組みとされています。

計算量で比べると、線形探索は O(n)、二分探索は O(log n) と言われています。データ数が多いほど差は大きく、たとえば100万件なら線形探索は最大100万回の比較、二分探索は約20回の比較で済むのが一般的とされています。

イメージしやすいのが、紙の電話帳から名前を探す場面です。先頭から順にめくる方法が線形探索、真ん中を開いて前半か後半かを判断する方法が二分探索に対応すると言われています。あなたが普段やっている探し方も、実は二分探索に近い場面が多いはずです。

探索の要点は、「整列されているか」で使える手順が変わるという関係性です。二分探索は速い反面、データが整列されている前提が必要になります。整列と探索を一組で押さえると、科目B の出題が読み取りやすくなるとされています。

あなたが整列・探索の説明で見かけた「再帰」とは、手順の中で自分自身を呼び出す考え方を指す言葉とされています。クイックソート・マージソート・二分探索は、いずれも再帰的に書けるアルゴリズムの代表例です。

再帰は「大きな問題を、同じ形の小さな問題に分解して解く」発想で整理されることが多いと言われています。分解の停止条件(これ以上分けない条件)をあらかじめ設けるのが基本です。

そして手順の速さを表す指標が計算量(Big O 記法)です。データ数 n が増えたとき、処理回数がどう増えていくかを表す目安として使われています。