PD-Dアルゴリズム・プログラミング · アルゴリズム
分割統治
Divide and Conquer
ぶんかつとうち
大きな問題を同じ種類の小さな部分問題に分割し、部分問題をそれぞれ（多くは再帰的に）解いて、その結果を統合して元の問題の解を得るアルゴリズムの設計方法。マージソート、クイックソート、2分探索、高速フーリエ変換が代表例である。半分ずつに分けて統合をO(n)で行える場合、全体はO(n log n)になることが多い。
共有:
Related
他の資格での定義
Past Exams
過去問での出題
過去問で 3 回出題（応用情報技術者試験 2・高度試験 午前Ⅰ 1）。うち 2 回は用語そのものを問う問題です。
出典: 独立行政法人情報処理推進機構（IPA）の過去問題。問題文は IPA のサイトの PDF で確認できます。「用語を問う問題」は、この用語の説明や特徴そのものを問う問題です。用語名で照合しているため、関係の薄い問題が含まれることがあります。
Related
関連キーワードの用語
PD-D併合のアルゴリズム
それぞれ整列済みの2つの列を、先頭どうしを比較して小さい方を取り出すことを繰り返し、1つの整列済みの列にまとめるアルゴリズム。マージともいい、要素数がm、nのときO(m＋n)で処理できる。マージソートの統合の段階や、キーの順に並んだ複数の順編成ファイル（マスタファイルとトランザクションファイルなど）をまとめる処理に使われる。
PD-Dクイックソート
基準値（ピボット）を選び、それより小さい要素と大きい要素のグループに分割する処理を、各グループに再帰的に繰り返す分割統治の整列のアルゴリズム。平均の計算量はO(n log n)で実用上最も速い部類だが、ピボットの選び方が悪いと分割が偏り最悪O(n²)になる。安定な整列ではない。