| English | 意味 |
|---|---|
| divide-and-conquer/dɪˈvaɪd ænd ˈkɒŋkə/ | 分治法 |
| merge sort/mɜːdʒ sɔːt/ | マージソート |
| merge/mɜːdʒ/ | 統合 |
再帰による探索とソート
- 同じ** divide-and-conquer（二分法・統合法）のアイデアが、再帰的な二分探索とマージソート**の駆動力となる。
- 問題を半分に分け、それぞれを解決し、統合する。
- 再帰的二分探索は、片側半分に自身が自身を呼び出して探索する。
- マージソートは、それぞれの半分をソートした上で、**統合（merge）**して整列された半分を組み合わせる。
再帰的二分探索
- ベースケース：空の範囲であれば、ターゲットは見つかっていない。
- 真ん中を見る。もしそれがターゲットなら、そのインデックスを返す。
- ターゲットが小さい場合は左半分で再帰し、大きい場合は右半分で行う。
- 各呼び出しで範囲が半分になる — これは同じ
O(log n)であり、再帰的に記述されたもの。
マージソート
- アレイを2つの半分へ分割し、それぞれの半分を再帰的にソートする。
- ベースケース：0個または1個の要素のみからなるアレイは既に整列済みである。
- マージ: ソートされた両方の半分を走査し、常に前方の小さい要素を取り出します。
n²ソートよりもはるかに速く、約n log nの処理量である。
なぜ二分法が勝つか
- 各ステップで問題を半分にすることで、
log n要因が生まれる。 - 大規模なアレイにおいて、マージソートの
n log nは、選択ソートや挿入ソートのn²よりも優れている。 - ベースケース（空または1要素）がすべての枝を停止させる。
- すべて共通する再帰の形状：下へ分けて、上に統合して戻る。
再帰的二分探索は「片方」の半分（ターゲットは片側にしかない）のみで再帰し、マージソートは「両方」の半分を再帰的にソートしてから統合する。 どちらもベースケースが必要である — 探索においては空の範囲は「見つかっていない」、マージソートにおいては0〜1要素のアレイは既に整列済みであることを意味する。これらが高速である理由は二分法（O(log n) とO(n log n)）にある。
[3, 1, 2, 4] のマージソート:
- ⟨
[3, 1]⟩ と[2, 4]に分割；それぞれソート → ⟨[1, 3]⟩ と[2, 4]。 - 統合：1、2、3、4を順に取り出す → ⟨
[1, 2, 3, 4]⟩。 - 各 merge は、順に小さい前方要素を選び取ります。
再帰的バイナリサーチは片方の半分に対して再帰します（基本ケース: 空の範囲＝未発見）で、O(log n)検索を行います。マージソートは両方の半分に対して再帰し、それらをマージします（基本ケース: 0個または1個の要素）で、O(n log n)ソートを行います。どちらもデバイド・アンド・コンカー: 分割して下へ進め、統合して上へ戻す — n²よりもはるかに速いです。
マージソートは半分に分けてから統合していく
単一要素は整列済み（基底ケース）であり、統合は上方に進む。
再帰的二項探索は...に対して再帰する
難易度 1/5 · 100 コイン + 今日初回完了時に小ボーナス付与
ターゲットは中央の片側にしかない。
マージソートは...に対して再帰する
難易度 1/5 · 100 コイン + 今日初回完了時に小ボーナス付与
それぞれの半分をソートしてから、2つの整列済みの半分を統合する。
マージソートの基底ケースは...の配列
難易度 1/5 · 100 コイン + 今日初回完了時に小ボーナス付与
1（または0）要素はソート不要。
マージソートの実行時間は約...
難易度 1/5 · 100 コイン + 今日初回完了時に小ボーナス付与
log n 層の分割、各層あたり n の作業量。
再帰的二項探索とマージソートはともに「 divide-and-conquer 」アルゴリズムである。
難易度 1/5 · 100 コイン + 今日初回完了時に小ボーナス付与
どちらも問題を半分にして再帰する。
半分の [1,3] と [2,4] に対する統合ステップを並べ替えてください。
難易度 3/5 · 200 コイン + 今日初回完了時に小ボーナス付与
常に小さい方の先頭要素を取る: 1, 2, 3, 4。