アルゴリズムとは

アルゴリズムとは何か？

アルゴリズムとは、ある問題を解決するための明確な手順の集まりです。 料理のレシピのように、入力（材料）を受け取り、決められたステップに従って処理し、 出力（完成した料理）を返します。

同じ問題に対して複数のアルゴリズムが存在することが多く、 それぞれ処理速度やメモリ使用量が異なります。適切なアルゴリズムを選ぶことで、 プログラムの性能を大幅に改善できます。

// 例：配列の中から最大値を見つけるアルゴリズム
function findMax(arr) {
  let max = arr[0];
  for (let i = 1; i < arr.length; i++) {
    if (arr[i] > max) {
      max = arr[i];
    }
  }
  return max;
}

console.log(findMax([3, 7, 2, 9, 1])); // 9

計算量とBig O記法

計算量（Complexity）とは、 アルゴリズムの効率を測る指標です。主に時間計算量（処理にかかる時間）と空間計算量（メモリ使用量）の2種類があります。

Big O記法は、入力サイズ n が大きくなったとき、 アルゴリズムの処理時間がどのように増加するかを表す記法です。

時間計算量の具体例

実際のコードでどのように計算量が変わるか見てみましょう。

// O(1) - 定数時間：配列のインデックスアクセス
function getFirst(arr) {
  return arr[0]; // 配列の大きさに関係なく一瞬
}

// O(n) - 線形時間：全要素を1回ずつ走査
function sum(arr) {
  let total = 0;
  for (let i = 0; i < arr.length; i++) {
    total += arr[i]; // n回のループ
  }
  return total;
}

// O(n^2) - 二乗時間：二重ループ
function hasDuplicate(arr) {
  for (let i = 0; i < arr.length; i++) {
    for (let j = i + 1; j < arr.length; j++) {
      if (arr[i] === arr[j]) return true;
    }
  }
  return false;
}

空間計算量

空間計算量は、アルゴリズムが使用するメモリの量を表します。 入力データ自体のサイズに加えて、処理中に追加で必要になるメモリ（補助空間）を考えます。

// O(1) 空間 - 追加メモリなし（変数のみ）
function findMax(arr) {
  let max = arr[0]; // 変数1つだけ
  for (const val of arr) {
    if (val > max) max = val;
  }
  return max;
}

// O(n) 空間 - 入力と同サイズの配列を新規作成
function reversed(arr) {
  const result = []; // n個分のメモリ
  for (let i = arr.length - 1; i >= 0; i--) {
    result.push(arr[i]);
  }
  return result;
}

アルゴリズムの選び方

アルゴリズムを選ぶ際は、以下のポイントを考慮します。

• 入力サイズ：データが小さければ単純なアルゴリズムでも十分
• 時間 vs 空間のトレードオフ：メモリを使って速度を上げるか、メモリを節約するか
• データの特性：ほぼソート済みか、ランダムか、重複があるか
• 実装の複雑さ：シンプルなコードの方が保守しやすい

// 例：重複チェック - O(n^2) vs O(n) のトレードオフ

// 方法1: O(n^2) 時間 / O(1) 空間 - メモリ節約
function hasDupSlow(arr) {
  for (let i = 0; i < arr.length; i++)
    for (let j = i + 1; j < arr.length; j++)
      if (arr[i] === arr[j]) return true;
  return false;
}

// 方法2: O(n) 時間 / O(n) 空間 - 速度重視
function hasDupFast(arr) {
  const seen = new Set();
  for (const val of arr) {
    if (seen.has(val)) return true;
    seen.add(val);
  }
  return false;
}