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

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

100万件のデータから目的の1件を探すとき、手順しだいで比較回数は「最大100万回」にも「約20回」にもなります。この途方もない差を生むのが、アルゴリズムです。

アルゴリズムとは、問題を解くための手順の設計図です。同じ答えにたどり着く手順でも、設計しだいで速さが大きく変わります。

以下では、この「回数の違い」をまず数で体感し、整列・探索・再帰、そして速さの物差しである計算量（Big O）まで順に押さえます。基本情報技術者の科目B にそのまま効きます。

1. 手順しだいで、速さは大きく変わる

同じ目的でも、手順は何通りも考えられます。「100人の名簿を名前順に並べる」なら、隣同士を比べて交換する方法、基準値で分ける方法、半分に割ってから統合する方法——どれも並び替えは終わりますが、かかる時間はまるで違います。この「同じ結果でも速さが違う」ことこそ、あなたがアルゴリズムを学ぶ理由です。

アルゴリズムの良し悪しは、正確さと速さ（計算量）の2つで測ります。あなたが科目B で解くのは、手順を1行ずつ追って動きを読み取る問題が中心です。だから「速さの差がどこから来るか」を先に体で分かっておくと、コードの読み取りが一段軽くなります。

2. 数で体感する探索 — 100万件を何回で見つけるか

探索は、データの中から目的の値を見つける手順です。代表が2つ。線形探索は先頭から順に1つずつ比べ、二分探索は整列済みのデータの真ん中を見て、前半か後半かで範囲を半分に絞ります。この「半分に絞る」がどれほど効くか、100万件で数えてみましょう。

半分に絞る操作を繰り返すと、100万件はおよそ20回で1件まで狭まります（2を20回かけると約104万だからです）。一方の線形探索は、運が悪ければ最後まで見て100万回。同じ「1件を探す」でも、約20回と最大100万回では桁が5つ違います。ただし二分探索には「整列済みであること」という前提があり、そこが次の整列の話につながります。

3. 整列(ソート)3種と計算量

二分探索の前提だった「整列済み」を作るのが、整列（ソート）です。科目B で問われるのは主に3種類で、速さがはっきり分かれます。

バブルソートの O(n²) は、件数が2倍になると手間が約4倍に膨らみます。1万件なら1億回規模の比較になり、実用に耐えません。クイック・マージの O(n log n) は、件数が増えても伸びがゆるやか。だから件数が大きいほど、後者が格段に速くなります。あなたが押さえたいのは、名前ではなく「分割する発想を持つ手順ほど速い」という規則性です。バブルは仕組みが素直なので読み取り問題の題材に、クイックとマージは再帰の典型例として問われます。

4. 再帰は大きな問題を小さく割る

クイックソート・マージソート・二分探索に共通するのが、再帰という書き方です。再帰とは、手順の中で自分自身を呼び出す考え方。「大きな問題を、同じ形の小さな問題に分けて解く」発想だと捉えると、腑に落ちます。

再帰でつまずかないコツは、停止条件を先に決めることです。「これ以上は分けない」という条件が無いと、分割が終わらず止まりません。マージソートなら「要素が1個になったら分けるのをやめる」がそれにあたります。あなたが再帰のコードを読むときは、まず停止条件を探すと、動きの全体像がつかめます。再帰で扱うスタックなどのデータのしまい方は データ構造とは と対で読むと、手順とデータが表裏で見えてきます。

5. Big O の読み方と科目Bでの問われ方

手順の速さを表す物差しが、計算量（Big O 記法）です。データ数 n が増えたとき、処理回数がどう伸びるかを表します。代表的な形を整理します。

科目B では、手順を読み取って「この処理の計算量はどれか」を選ぶ形が定番です。二重ループが出てきたら O(n²)、半分ずつ絞る処理なら O(log n)、とコードの形から計算量を見抜く練習が効きます。あなたがつまずきやすいのは、件数が小さいと速度差を感じにくい点。データが小さいうちは O(n²) でも一瞬で終わるので、実務でも見落とされがちです。差が牙をむくのは件数が増えたとき。あなたがこの「伸び方の違い」を意識できると、手順の良し悪しを数で語れます。

次のステップ

アルゴリズムが科目B のどこで問われるかは、基本情報技術者 試験全体概要 で範囲を見ておくと、学習の進め方が定まります。

手順の読み取りに慣れるなら、基本情報技術者 科目B アルゴリズムの問題集 で、実際のコードを追う設問に当たっておくのが近道です。