行列90度回転: 転置 + 行反転アルゴリズム解析

1. アルゴリズム概要

このアルゴリズムは2段階のアプローチを採用します：

  1. Step 1: 行列を転置（対角線に対して反転）
  2. Step 2: 各行を左右反転

この2つの操作を組み合わせることで、90度時計回りの回転を実現します。

2. Step 1: 転置（Transpose）の詳細解析

転置の概念

転置とは、行列の行と列を入れ替える操作です。要素 matrix[i][j] が matrix[j][i] と交換されます。

// Step 1: 転置の実装 for (let i = 0; i < n; i++) { for (let j=i + 1; j < n; j++) { // ⚠️ j = i + 1 から開始（重要！） const temp: number = matrix[i][j]; matrix[i][j] = matrix[j][i]; // (i,j) ← (j,i) matrix[j][i] = temp; // (j,i) ← 元の(i,j) } }

⚠️ 重要なポイント: なぜ j = i + 1 から？

理由: 対角線より上の部分のみを処理することで、各要素ペアを1回だけ交換

もし j = 0 から始めると: 同じ要素ペアを2回交換してしまい、元に戻ってしまう

対角線要素: matrix[i][i] は交換不要（自分自身との交換）

3×3行列での転置デモンストレーション

初期状態:

1
2
3
4
5
6
7
8
9
処理対象: 対角線より上の要素のみ
交換ペア: (0,1)↔(1,0), (0,2)↔(2,0), (1,2)↔(2,1)
→

転置後:

1
4
7
2
5
8
3
6
9
結果: 行と列が入れ替わった
対角線要素（1,5,9）は変化なし

転置処理の詳細な反復解析

3. Step 2: 行反転（Reverse Rows）の詳細解析

行反転の実装

// Step 2: 各行を反転 for (let i = 0; i < n; i++) { matrix[i].reverse(); // 配列の組み込みメソッドを使用 } // reverse()の内部動作（参考）: // [a, b, c] → [c, b, a] // 先頭と末尾から順次交換

行反転のデモンストレーション

転置後の状態:

1
4
7
2
5
8
3
6
9
→

各行反転後（最終結果）:

7
4
1
8
5
2
9
6
3
各行の変化:
[1,4,7] → [7,4,1]
[2,5,8] → [8,5,2]
[3,6,9] → [9,6,3]

4. 完全なアルゴリズムデモンストレーション

4×4行列での完全な処理過程

5. なぜこの方法で90度回転になるのか？

数学的説明

// 元の座標 (i, j) の移動を追跡: // Step 1: 転置 (i, j) → (j, i) // Step 2: 行反転 (行jの要素を反転) (j, i) → (j, n-1-i) // 結合した結果: (i, j) → (j, n-1-i) // これは90度時計回りの回転公式と一致！

例: 4×4行列での座標変換

• 元の(0,1) → 転置後(1,0) → 行反転後(1,3) ✓

• 元の(2,0) → 転置後(0,2) → 行反転後(0,1) ✓

• 元の(3,2) → 転置後(2,3) → 行反転後(2,0) ✓

6. 計算量分析

時間計算量: O(n²)

Step 1 (転置): n×n要素の約半分を処理 → O(n²/2) = O(n²)

Step 2 (行反転): n行 × 各行n/2要素 → O(n²/2) = O(n²)

合計: O(n²) + O(n²) = O(n²)

空間計算量: O(1)

転置: 一時変数temp のみ使用

行反転: Array.reverse() はin-place操作

総メモリ: 追加配列不要、定数空間のみ

7. アルゴリズム比較

転置+行反転の利点

  • 実装が直感的で理解しやすい
  • 2つの単純な操作の組み合わせ
  • デバッグが容易
  • Array.reverse()の最適化を活用
  • コードが短くて読みやすい

レイヤー回転との比較

  • 2回の配列走査が必要
  • キャッシュ効率が若干劣る可能性
  • reverse()の内部実装に依存

結論: 実用的には性能差は僅少で、コードの可読性が重要な場合は優秀な選択

8. 実装時の注意点

よくある間違いとその対策