基本情報技術者試験 アルゴリズム・データ構造の頻出ポイント完全解説
アルゴリズムとデータ構造は、基本情報技術者試験の科目Bでも中心となる重要分野です。 プログラミング未経験だと身構えてしまいますが、「探索」「ソート」「計算量」「基本データ構造」の 4つの柱を理解すれば多くの問題に対応できます。このページでは各テーマの要点を整理します。
1. 探索アルゴリズム
線形探索
データを先頭から順に1つずつ調べる、最も単純な探索方法です。 n個のデータがあれば最悪n回の比較が必要で、計算量はO(n)。 データが並んでいなくても使える反面、データが多いと時間がかかります。
2分探索
ソート済みのデータに対して、中央の要素と比較しながら探索範囲を半分ずつ絞り込む方法です。 1回比較するごとに候補が半分になるため、計算量はO(log n)と非常に高速。 ただし「データがソート済みである」という前提が必須です。 100万件のデータでも約20回の比較で見つけられます。
2. 代表的なソートアルゴリズム
| ソート名 | 仕組み | 平均計算量 |
|---|---|---|
| バブルソート | 隣り合う要素を比較して交換 | O(n²) |
| 選択ソート | 最小値を選んで先頭に置く | O(n²) |
| 挿入ソート | 整列済み部分に1つずつ挿入 | O(n²) |
| クイックソート | 基準値で分割を繰り返す | O(n log n) |
| マージソート | 分割して整列しながら統合 | O(n log n) |
試験では「各ソートの計算量」と「仕組みの特徴」が問われます。 クイックソートは平均的に高速ですが、最悪の場合はO(n²)になる点も覚えておきましょう。
3. 計算量（オーダー記法）
アルゴリズムの効率を表すのが計算量で、O（オー）記法で表します。 データ数nが増えたときに処理時間がどれくらい増えるかを示します。効率の良い順に並べると次のとおりです。
- O(1)：データ数によらず一定（最速）。配列の添字アクセスなど
- O(log n)：データが増えてもほぼ増えない。2分探索
- O(n)：データ数に比例。線形探索
- O(n log n)：効率的なソート。クイック・マージ
- O(n²)：データ数の2乗。単純なソート（遅い）
4. 基本データ構造
- 配列：連続した領域にデータを並べる。添字で高速アクセス（O(1)）
- 連結リスト：各要素が次の要素を指す。挿入・削除が得意
- スタック：後入れ先出し（LIFO）。関数呼び出しの管理など
- キュー：先入れ先出し（FIFO）。待ち行列の処理など
- 木（ツリー）：階層構造。二分探索木は「左＜親＜右」
- ハッシュ：キーから値を高速に取り出す。平均O(1)
「スタック＝LIFO」「キュー＝FIFO」の対比は頻出です。スタックは積み重ねた皿、キューは行列をイメージすると覚えやすいです。
5. 例題で確認
よくある質問（FAQ）
Q. プログラミング未経験でもアルゴリズムは理解できますか？
A. はい。まずは「探索」「ソート」「計算量」「データ構造」の概念を日本語で理解することが大切です。コードを書けなくても用語と仕組みで多くの問題に対応できます。
Q. 計算量の順番が覚えられません。
A. 「O(1) ＜ O(log n) ＜ O(n) ＜ O(n log n) ＜ O(n²)」の順を、具体例（2分探索＝O(log n)等）とセットで覚えると定着します。
Q. ソートの種類が多くて混乱します。
A. まず「O(n²)の単純ソート」と「O(n log n)の高速ソート」の2グループに分けて整理すると覚えやすいです。