アルゴリズムの比較
1. 二分探索法 (Binary Search)
長所
- 高速性: ソート済みの配列に対して$O(log n)$の時間計算量で要素を探索可能。
- シンプルさ: 実装が比較的簡単で、動作原理を理解しやすい。
- 効率性: メモリ消費が少なく、配列の範囲外アクセスを防ぐことができる。
短所
- ソートが前提条件: データがソートされていない場合、事前にソートが必要$O(n log n)$.
- 動的データへの非対応: 配列やリストの要素が頻繁に更新される場合は効率が悪化。
- 特定の構造に依存: 配列や単調性がある関数の探索にしか利用できない。
適用場面
- ソート済みのデータから特定の要素や条件を満たす値を効率よく見つける必要がある場合。
- 単調増加/単調減少な関数で特定の閾値を探索する問題（例: 答えが「Yes/No」で分岐する問題）。
2. 貪欲法 (Greedy Algorithm)
長所
- 高速性: その時点で最適な選択を行うことで、計算量を減らし、効率的に解を求められる（問題によっては $O(n)$。
- 直感的な設計: 解法が直感的であり、特定の制約を最小化/最大化する問題に適用しやすい。
- 低い実装コスト: コードが比較的簡潔になりやすい。
短所
- 局所最適化: 各ステップでの最適解が必ずしも全体の最適解に繋がらないことがある。
- 適用範囲の限定: 問題によっては貪欲法が有効でない場合が多い（全体の最適解を保証するために証明が必要）。
- 競合の管理が難しい: 一度選んだ選択肢を修正できないため、結果が間違っていてもリカバリーが難しい。
適用場面
- 部分問題の最適解が全体の最適解に繋がる場合（例: 活動選択問題、クラススケジューリング）。
- 近似解が許容される問題（例: ハフマン符号、配達ルートの計算）。
3. 動的計画法 (Dynamic Programming, DP)
長所
- 全体最適解の保証: 問題を分割し、サブ問題を最適に解くことで全体の最適解を見つけられる。
- 重複計算の削減: メモ化やテーブルに結果を保存することで、再計算を回避し効率化。
- 多様な問題に対応可能: 組み合わせ最適化、文字列操作、配列の区間問題など幅広い応用範囲。
短所
- 実装が複雑: 状態や遷移の設計が難しく、ミスが発生しやすい。
- 高いメモリ消費: 特に2次元以上のテーブルを使用する場合、メモリが不足することがある。
- 計算量が高くなる場合がある: 多くの状態を扱う場合、計算量が $O(n^2)$ や $O(n^3)$になることがある。
適用場面
- 問題が最適部分構造（サブ問題の最適解が全体の最適解に利用できる）を持つ場合。
- 問題が重複部分問題（同じ問題を複数回計算する必要がある）を持つ場合。
- 例: ナップサック問題、最長共通部分列（LCS）、最短経路問題（ベルマンフォード法など）。