4-5. 演習問題

問題1：選択問題

1-1. バブルソートの平均計算量として最も適切なのはどれか。

A. O(n²)
B. O(n log n)
C. O(1)

解答と解説

正解：A. O(n²)

A が正しい。バブルソートは n 要素に対して最大 n×(n-1)/2 回の比較を行うため O(n²) になる。
B は誤り。O(n log n) はクイックソートやマージソートの計算量である。
C は誤り。O(1) は定数時間であり、ソートでは起こりえない。

n=1,000 のデータでは最大約 50 万回の比較が発生する。

1-2. Big O 記法 O(n log n) の説明として最も適切なのはどれか。

A. O(n²) より増加が緩やかで、データが 10 倍になっても処理時間は約 10〜20 倍程度に収まる
B. データ量に関係なく処理時間は一定である
C. データ量の 2 乗に比例して処理時間が増える

解答と解説

正解：A. O(n²) より増加が緩やかで、データが 10 倍になっても処理時間は約 10〜20 倍程度に収まる

A が正しい。n=10→100 では 33→664（約 20 倍）、n=100→1,000 では 664→9,966（約 15 倍）と、データが 10 倍になっても 100 倍には届かない。
B は誤り。それは O(1) の説明である。
C は誤り。それは O(n²) の説明であり、データ 10 倍 → 処理時間 100 倍になる。

O(n log n) と O(n²) の差は大きい。n=1,000 では 9,966 対 1,000,000 と約 100 倍の開きがある。

1-3. クイックソートが「平均 O(n log n)」になる理由として最も適切なのはどれか。

A. pivot によってデータが半分ずつに分割され、再帰の深さが log n 程度になるから
B. 隣り合う要素だけを比較するから
C. 配列を逆順にするだけだから

解答と解説

正解：A. pivot によってデータが半分ずつに分割され、再帰の深さが log n 程度になるから

A が正しい。分割統治法の特徴で、半分に割り続けると深さは log₂(n) になる。各深さで合計 n 回の比較を行うため n × log n になる。
B は誤り。それはバブルソートの説明である。
C は誤り。逆順は O(n) でできる。

ただし pivot の選び方が悪い（常に最大値や最小値を pivot にする）場合は最悪 O(n²) になる。

1-4. 素朴な再帰で実装した fib(n) の計算量として最も適切なのはどれか。

A. O(2ⁿ)
B. O(n)
C. O(log n)

解答と解説

正解：A. O(2ⁿ)

A が正しい。fib(n) が fib(n-1) と fib(n-2) を呼ぶため、呼び出し回数はおよそ 2ⁿ に増える。
B は誤り。O(n) になるのはメモ化または反復で実装したときである。
C は誤り。O(log n) は二分探索などで現れる計算量である。

n=40 では約 3 億回の呼び出しが発生し、数百ミリ秒〜1 秒程度かかる。n=45 では約 37 億回で数秒、n=50 では約 407 億回と実用不可能な時間になる。

1-5. メモ化が計算量を O(2ⁿ) から O(n) に改善できる理由として最も適切なのはどれか。

A. 計算済みの結果をキャッシュに保存し、同じ引数の再計算を省略できるから
B. ループを使うから
C. 再帰を使わないから

解答と解説

正解：A. 計算済みの結果をキャッシュに保存し、同じ再計算を省略できるから

A が正しい。fib(k) を初めて呼んだときだけ計算してキャッシュに保存する。2回目以降はキャッシュから即座に返すため、各 k に対して 1 回しか計算しない。
B は誤り。ループを使うのは反復法の説明であり、メモ化は再帰のまま高速化する。
C は誤り。メモ化は再帰を使いつつ高速化する手法である。

このように「同じ部分問題を何度も解かない」工夫を**動的計画法（DP）**と呼ぶ。

1-6. ソートの「安定性」の説明として最も適切なのはどれか。

A. 同じ値を持つ要素の相対的な順序が、整列後も保たれる性質
B. どんな入力でも最悪計算量が一定である性質
C. メモリ使用量が O(1) である性質

解答と解説

正解：A. 同じ値を持つ要素の相対的な順序が、整列後も保たれる性質

A が正しい。たとえば同じ価格の書籍が複数あるとき、安定ソートでは元の順番が維持される。
B は誤り。それは最悪計算量の安定性の話であり、ソートの「安定性」ではない。
C は誤り。それは「インプレース（追加メモリなし）」の説明である。

実務では「名前でソートしてから価格でソートした結果、同じ価格のものが名前順になっている」ような場面で安定性が重要になる。

問題2：穴埋め問題

次の文章の空欄を埋めてください。

アルゴリズムの計算量をデータ量 n の関数で表す記法を （　　　） 記法という。
バブルソートの平均計算量は （　　　） である。
クイックソートの平均計算量は （　　　） である。
素朴な再帰で実装したフィボナッチの計算量は （　　　） である。
計算済みの結果を保存して再計算を省く手法を （　　　） という。
同じ値の要素の順序が整列後も保たれる性質を （　　　） という。

解答欄

解答と解説

Big O

O(f(n)) という形でデータ量 n に対する処理量の増え方を表す。定数倍の差は無視し、増加の「傾き」だけを見る。

O(n²)

n 要素に対して最大 n×(n-1)/2 回の比較が発生する。

O(n log n)

pivot による分割で再帰の深さが log n になり、各深さで n 回の比較をするため。

O(2ⁿ)

1 回の呼び出しが 2 回の再帰呼び出しを生むため、指数的に爆発する。

メモ化（memoization）

Map などにキャッシュして同じ計算を繰り返さない。動的計画法（DP）の基本技法である。

安定性（stable）

安定ソートの代表例はバブルソート・挿入ソート・マージソート。クイックソートは一般に不安定である。

問題3：記述問題

3-1. バブルソートとクイックソートで、データ量が 1,000 件の場合の計算量の違いを数値で説明してください。

解答欄

解答と解説

3-1. 例

バブルソートは O(n²) なので n=1,000 では最大約 1,000,000 回の比較が発生する。クイックソートは平均 O(n log n) なので約 1,000 × 10 = 10,000 回程度の比較で済む。これはおよそ 100 倍の差である。n=10,000 では差が 1,000 倍に広がる。「同じ結果を出す」アルゴリズムでも、計算量の違いは実用性に直結する。

3-2. 素朴な再帰で fib(50) を計算すると非常に遅くなる理由を、呼び出しツリーの構造を使って説明してください。

解答欄

解答と解説

3-2. 例

fib(n) は fib(n-1) と fib(n-2) を呼び、それぞれがさらに2回ずつ呼ぶ。呼び出しツリーは深さ n の二分木になるため、葉ノードの数（実際に計算する回数）は約 2ⁿ になる。 fib(5) は fib(3) を 2 回、fib(2) を 3 回と、同じ値を何度も再計算している。 n=50 では約 407 億回の呼び出しが発生し、現実的な時間内には終わらない。

3-3. メモ化と反復の両方が O(n) であるにもかかわらず、実務で反復が好まれることが多い理由を説明してください。

解答欄

解答と解説

3-3. 例

メモ化は再帰呼び出しのたびにスタックフレームを積む。n が非常に大きいと「スタックオーバーフロー」を起こすリスクがある。また、Map への読み書きコストや再帰コールの関数呼び出しオーバーヘッドも積み重なる。反復は変数を 2 つ更新するだけなのでメモリ効率が良く、オーバーヘッドも最小限である。 Big O の表記は同じ O(n) でも、定数倍の差や実装の安全性が実務では影響する。

3-4. アルゴリズムを選ぶときに計算量だけを見ればよいとは限らない理由を、実務の観点から説明してください。

解答欄

解答と解説

3-4. 例

計算量は漸近的な評価であり、定数倍の差は無視される。しかし実際には、実装のシンプルさ・安定性・メモリ消費・ライブラリの有無なども重要である。たとえば数十件のデータならバブルソートでも十分速く、クイックソートを実装するコストが見合わない。また「安定ソートが必要」という要件があればマージソートを選ぶ。「速い」だけでなく「正しく、保守しやすく、要件を満たす」アルゴリズムを選ぶことが大切である。

問題4：ハンズオン

ハンズオン 4-1：ソートアルゴリズムの実装と可視化

バブルソートと選択ソートのTODOを実装し、各ステップの配列状態を目で追って動きを確認せよ。

取り組む内容

bubbleSort のTODO部分（比較と swap）を実装する
selectionSort のTODO部分（最小値探索と swap）を実装する
実行してステップ数の違いを確認する（比較回数は同じでも swap 回数が違う）

実行プレイグラウンド

編集内容は自動保存されます / Ctrl+Enter でも実行できます

// ステップ表示ヘルパー（変更不要）
let stepCount = 0;
function printStep(arr, i, j, action) {
stepCount++;
const row = arr.map((v, idx) => {
  const s = String(v).padStart(2);
  if (idx === i && idx === j) return `«${s}»`;
  if (idx === i) return `(${s})`;
  if (idx === j) return `[${s}]`;
  return `  ${s} `;
}).join(" ");
if (action) console.log(`Step ${String(stepCount).padStart(3)}: ${row}  ← ${action}`);
else        console.log(`Step ${String(stepCount).padStart(3)}: ${row}`);
}

// TODO: バブルソートを実装する
// - 外ループ i=0..n-2、内ループ j=0..n-i-2
// - a[j] > a[j+1] なら swap し printStep(a, j, j+1, "swap") を呼ぶ
// - そうでなければ printStep(a, j, j+1, "") を呼ぶ
function bubbleSort(arr) {
const a = [...arr];
const n = a.length;


return a;
}

// TODO: 選択ソートを実装する
// - 外ループ i=0..n-2 で「未整列の先頭」を決める
// - 内ループで a[i..n-1] の最小値インデックス minIdx を探す
//   → 探索中は printStep(a, i, j, "") を呼ぶ
// - a[i] !== a[minIdx] なら swap し printStep(a, i, minIdx, "swap") を呼ぶ
function selectionSort(arr) {
const a = [...arr];
const n = a.length;


return a;
}

const data = [5, 3, 8, 1, 9, 2, 7, 4, 6];

console.log("=== バブルソート ===");
console.log("初期:", data);
stepCount = 0;
const bResult = bubbleSort(data);
console.log("結果:", bResult);
console.log("ステップ数:", stepCount);

console.log("");
console.log("=== 選択ソート ===");
console.log("初期:", data);
stepCount = 0;
const sResult = selectionSort(data);
console.log("結果:", sResult);
console.log("ステップ数:", stepCount);

出力

「実行」を押すと、ここに結果が表示されます。

確認したいポイント

各ステップで () と [] が比較対象の2要素を示す — 交換が起きる場所を目で追う
バブルソートは毎パスで大きい値が末尾に「浮いていく」動きを確認する
選択ソートは「未整列部分の最小値を先頭に持ってくる」動きを確認する
どちらも比較回数は同程度だが、バブルは swap が多く、選択は swap が少ないことを確認する

ハンズオン 4-2：フィボナッチの計算量比較

3つの実装（素朴な再帰・メモ化・反復）を実行して、n が増えたときの性能差を数値で確認せよ。実装はすでに完成しているため、実行して結果を観察するだけでよい。

取り組む内容

そのまま実行し、n=35 での実行時間を比較する
LIMIT = 35 を 40 に変えて再実行し、再帰がさらに遅くなることを確認する
LIMIT = 45 では再帰が実用不能になることを確認する（再帰だけコメントアウトして比較する）

実行プレイグラウンド

編集内容は自動保存されます / Ctrl+Enter でも実行できます

// 素朴な再帰 O(2^n)
function fibNaive(n) {
if (n <= 1) return n;
return fibNaive(n - 1) + fibNaive(n - 2);
}

// メモ化再帰 O(n)
function fibMemo(n, memo = new Map()) {
if (n <= 1) return n;
if (memo.has(n)) return memo.get(n);
const result = fibMemo(n - 1, memo) + fibMemo(n - 2, memo);
memo.set(n, result);
return result;
}

// 反復処理 O(n)
function fibIter(n) {
if (n <= 1) return n;
let prev = 0, curr = 1;
for (let i = 2; i <= n; i++) {
  [prev, curr] = [curr, prev + curr];
}
return curr;
}

// 計測ヘルパー
function measure(fn, n, label) {
const start = performance.now();
const result = fn(n);
const ms = (performance.now() - start).toFixed(3);
console.log(`${label.padEnd(12)} fib(${n}) = ${result}  [${ms} ms]`);
}

const LIMIT = 35; // ← ここを 40, 45 と変えて観察する

console.log(`=== fib(${LIMIT}) の計算量比較 ===`);
measure(fibNaive, LIMIT, "素朴な再帰");
measure((n) => fibMemo(n), LIMIT, "メモ化再帰");
measure(fibIter,  LIMIT, "反復処理");

console.log("");
console.log("=== 小・中・大 でのステップ感 ===");
for (const n of [10, 20, 30, LIMIT]) {
const start = performance.now();
fibNaive(n);
const ms = (performance.now() - start).toFixed(3);
console.log(`再帰 fib(${String(n).padStart(2)}) : ${ms} ms`);
}

出力

「実行」を押すと、ここに結果が表示されます。

確認したいポイント

LIMIT = 35 で素朴な再帰が数十ms〜100ms 程度かかる一方、メモ化・反復はほぼ瞬時（0.01ms 以下）であることを確認する
LIMIT = 40 で素朴な再帰の時間が LIMIT = 35 の約 11 倍（φ⁵ 倍、φ ≈ 1.618）になることを確認する
LIMIT = 45 では素朴な再帰が数秒〜十数秒かかる（確認したらコメントアウト推奨）
3 つすべての関数が「同じ正しい答え」を返すことも確認する — 速さだけが違う

解答と解説

ハンズオン 4-1：バブルソートと選択ソートの実装例

function bubbleSort(arr) {
  const a = [...arr];
  const n = a.length;
  for (let i = 0; i < n - 1; i++) {
    for (let j = 0; j < n - i - 1; j++) {
      if (a[j] > a[j + 1]) {
        [a[j], a[j + 1]] = [a[j + 1], a[j]];
        printStep(a, j, j + 1, "swap");
      } else {
        printStep(a, j, j + 1, "");
      }
    }
  }
  return a;
}

function selectionSort(arr) {
  const a = [...arr];
  const n = a.length;
  for (let i = 0; i < n - 1; i++) {
    let minIdx = i;
    for (let j = i + 1; j < n; j++) {
      printStep(a, i, j, "");
      if (a[j] < a[minIdx]) minIdx = j;
    }
    if (minIdx !== i) {
      [a[i], a[minIdx]] = [a[minIdx], a[i]];
      printStep(a, i, minIdx, "swap");
    }
  }
  return a;
}

出力の読み方

(5) は i 番目の要素、[3] は j 番目の要素
← swap! が出た行の直後で2つの値が入れ替わっている
バブルソートは毎パスで右端に大きい値が確定する動きが見える
選択ソートは比較数は同程度でも交換（swap）回数が少ない

ハンズオン 4-2：フィボナッチの性能差の仕組み

LIMIT を 5 増やすと素朴な再帰の時間は約 φ⁵ ≈ 11 倍になる（フィボナッチの増加率 φ ≈ 1.618 の性質）
メモ化・反復は n が 10 倍になっても時間は 10 倍程度にしか増えない（O(n) の性質）
fib(40) で再帰は約 3 億回呼ばれるが、反復はたった 40 回のループで済む

計算量の選択は「コードが動くか」ではなく「実用的な速度で動くか」を決める。 O(2ⁿ) のコードは小さい入力では問題なくても、入力が増えた瞬間に崩壊する。