分割統治法

問題を小さな部分問題に分割し、各部分問題を再帰的に解いた後、結果を統合して全体の解を得る設計手法。マージソート、クイックソート、二分探索、FFTなどの基盤となるアルゴリズム設計パラダイム。

大きな問題を同じ種類の小さな部分問題に分割し、部分問題をそれぞれ（多くは再帰的に）解いて、その結果を統合して元の問題の解を得るアルゴリズムの設計方法。マージソート、クイックソート、2分探索、高速フーリエ変換が代表例である。半分ずつに分けて統合をO(n)で行える場合、全体はO(n log n)になることが多い。

最適化問題を部分問題に分割し、各部分問題の解を記憶しながら全体の最適解を求めるアルゴリズム設計手法。重複する部分問題を再計算せずに済むため効率的。ナップサック問題や最短経路問題に応用される。

直前の2項を足した値が次の項になる数列。1,1,2,3,5,8,13…と続く。再帰処理の例題として頻出で、素直に再帰で書くと同じ計算を何度も繰り返すため、途中結果を保存する動的計画法で高速化できる。

アルゴリズムの実行に必要な計算ステップ数を入力サイズの関数として表したもの。オーダー記法O(n)で表現され、O(1)、O(log n)、O(n)、O(n log n)、O(n²)などがある。アルゴリズムの効率を評価する基本指標。

隣接する要素を比較して交換を繰り返すことでデータを整列するアルゴリズム。平均・最悪計算量ともにO(n²)で効率は良くないが、アルゴリズムが単純で理解しやすい。安定ソート。

未整列部分から最小値（または最大値）を見つけて先頭に移動する操作を繰り返す整列アルゴリズム。計算量はO(n²)で、交換回数が少ないがデータ比較は多い。不安定ソート。

未整列部分の先頭要素を整列済み部分の適切な位置に挿入する操作を繰り返す整列アルゴリズム。平均・最悪計算量はO(n²)だが、ほぼ整列済みのデータに対してはO(n)で高速。安定ソート。