Day 1: アルゴリズム入門とBig O記法

今日学ぶこと

• アルゴリズムとデータ構造の基本概念
• なぜアルゴリズムを学ぶ必要があるのか
• Big O記法による計算量の表現
• 主要な計算量クラスの理解

---

アルゴリズムとは何か

アルゴリズムとは、ある問題を解決するための手順を明確に定義したものです。料理のレシピのように、入力を受け取り、一連のステップを実行して、期待する出力を生成します。

// Simple algorithm: find the largest number in an array
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

---

データ構造とは何か

データ構造とは、データを整理・格納する方法です。適切なデータ構造を選ぶことで、アルゴリズムの効率が大きく変わります。

flowchart TB
    subgraph DS["データ構造の分類"]
        direction TB
        Linear["線形構造"]
        NonLinear["非線形構造"]
    end
    subgraph L["線形"]
        A["配列"]
        B["連結リスト"]
        C["スタック"]
        D["キュー"]
    end
    subgraph NL["非線形"]
        E["木"]
        F["グラフ"]
        G["ハッシュテーブル"]
    end
    Linear --> L
    NonLinear --> NL
    style DS fill:#3b82f6,color:#fff
    style L fill:#22c55e,color:#fff
    style NL fill:#8b5cf6,color:#fff

---

なぜアルゴリズムを学ぶのか

同じ問題でも、アルゴリズムの選び方で処理速度が劇的に変わります。

例：リストから値を探す

線形探索：先頭から順番に探す

function linearSearch(arr, target) {
  for (let i = 0; i < arr.length; i++) {
    if (arr[i] === target) return i;
  }
  return -1;
}

二分探索：ソート済みリストを半分ずつ絞り込む

function binarySearch(arr, target) {
  let left = 0;
  let right = arr.length - 1;

  while (left <= right) {
    const mid = Math.floor((left + right) / 2);
    if (arr[mid] === target) return mid;
    if (arr[mid] < target) left = mid + 1;
    else right = mid - 1;
  }
  return -1;
}

100万個の要素から探す場合：

• 線形探索: 最大100万回の比較
• 二分探索: 最大20回の比較

この違いを正確に表現するのが Big O記法 です。

---

Big O記法

Big O記法は、入力サイズ n が大きくなったときに、アルゴリズムの実行時間やメモリ使用量がどのように増加するかを表します。

定数項や係数は無視する

Big O記法では、最も支配的な項だけを残します。

正確な計算量	Big O
3n + 5	O(n)
2n² + 3n + 1	O(n²)
5	O(1)
n + log n	O(n)

---

主要な計算量クラス

flowchart LR
    subgraph Fast["高速"]
        O1["O(1)\n定数時間"]
        Olog["O(log n)\n対数時間"]
    end
    subgraph Medium["中程度"]
        On["O(n)\n線形時間"]
        Onlog["O(n log n)\n線形対数時間"]
    end
    subgraph Slow["低速"]
        On2["O(n²)\n二乗時間"]
        O2n["O(2ⁿ)\n指数時間"]
    end
    O1 --> Olog --> On --> Onlog --> On2 --> O2n
    style Fast fill:#22c55e,color:#fff
    style Medium fill:#f59e0b,color:#fff
    style Slow fill:#ef4444,color:#fff

O(1) - 定数時間

入力サイズに関係なく、常に同じ時間で完了します。

// Array access by index: O(1)
function getFirst(arr) {
  return arr[0];
}

O(log n) - 対数時間

入力が倍になっても、処理回数は1回しか増えません。

// Binary search: O(log n)
function binarySearch(arr, target) {
  let left = 0;
  let right = arr.length - 1;
  while (left <= right) {
    const mid = Math.floor((left + right) / 2);
    if (arr[mid] === target) return mid;
    if (arr[mid] < target) left = mid + 1;
    else right = mid - 1;
  }
  return -1;
}

O(n) - 線形時間

入力サイズに比例して処理時間が増えます。

// Sum all elements: O(n)
function sum(arr) {
  let total = 0;
  for (const num of arr) {
    total += num;
  }
  return total;
}

O(n log n) - 線形対数時間

効率的なソートアルゴリズムの典型的な計算量です。

// Merge sort: O(n log n)
function mergeSort(arr) {
  if (arr.length <= 1) return arr;
  const mid = Math.floor(arr.length / 2);
  const left = mergeSort(arr.slice(0, mid));
  const right = mergeSort(arr.slice(mid));
  return merge(left, right);
}

O(n²) - 二乗時間

ネストされたループで入力全体を2回走査する場合に発生します。

// Bubble sort: O(n²)
function bubbleSort(arr) {
  const n = arr.length;
  for (let i = 0; i < n; i++) {
    for (let j = 0; j < n - i - 1; j++) {
      if (arr[j] > arr[j + 1]) {
        [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
      }
    }
  }
  return arr;
}

O(2ⁿ) - 指数時間

入力が1増えるごとに処理時間が倍になります。

// Fibonacci (naive recursive): O(2ⁿ)
function fib(n) {
  if (n <= 1) return n;
  return fib(n - 1) + fib(n - 2);
}

---

実行時間の比較

n = 1,000の場合の比較：

計算量	操作回数	例
O(1)	1	配列のインデックスアクセス
O(log n)	~10	二分探索
O(n)	1,000	線形探索
O(n log n)	~10,000	マージソート
O(n²)	1,000,000	バブルソート
O(2ⁿ)	天文学的数字	素朴な再帰

---

空間計算量

時間だけでなく、メモリ使用量も重要です。

// O(1) space: in-place modification
function reverseInPlace(arr) {
  let left = 0;
  let right = arr.length - 1;
  while (left < right) {
    [arr[left], arr[right]] = [arr[right], arr[left]];
    left++;
    right--;
  }
  return arr;
}

// O(n) space: creates a new array
function reverseNew(arr) {
  return arr.slice().reverse();
}

---

まとめ

概念	説明
アルゴリズム	問題を解決する手順の明確な定義
データ構造	データを整理・格納する方法
Big O記法	計算量の増加率を表す記法
時間計算量	処理にかかる時間の増加率
空間計算量	メモリ使用量の増加率

重要ポイント

1. アルゴリズムの選択は実行速度に大きく影響する
2. Big O記法は最悪ケースでの増加率を表す
3. 定数項や低次の項は無視する
4. 時間と空間のトレードオフを意識する

---

練習問題

問題1: 基本

次のコードの時間計算量をBig O記法で答えてください。

function mystery(n) {
  let count = 0;
  for (let i = 1; i < n; i *= 2) {
    count++;
  }
  return count;
}

問題2: 応用

次のコードの時間計算量を求めてください。

function process(arr) {
  for (let i = 0; i < arr.length; i++) {
    for (let j = i + 1; j < arr.length; j++) {
      console.log(arr[i], arr[j]);
    }
  }
}

チャレンジ問題

ソート済み配列の中から、合計が特定の値になる2つの要素のペアを見つけるアルゴリズムを O(n) で実装してください。

---

参考リンク

• Big O Cheat Sheet
• MDN - Array
• Wikipedia - Time complexity

---

次回予告: Day 2では「配列と連結リスト」について学びます。2つの基本データ構造の違いと使い分けを理解しましょう。