Recursion · 3 of 3
Divide and conquer
Split an input in half, solve each half with a recursive call and combine the answers, with merge sort and its O(n log n) cost as the example.
Books1
Links2
- 递归 & 分治 (Recursion and divide and conquer) What recursion costs and how to reduce it, how divide and conquer splits a problem, and how both differ from plain enumeration, with worked examples. oi-wiki.org (opens in a new tab)
- Algorithms, Chapter 1: Recursion Merge sort and quicksort as divide and conquer, with proofs that they sort and recursion trees for balanced and lopsided splits. Parts of this page adapt this chapter's text, licensed CC BY 4.0 (creativecommons.org/licenses/by/4.0), with changed wording, examples and code. jeffe.cs.illinois.edu (opens in a new tab)
More links5
- CP-Algorithms – Divide and Conquer DPcp-algorithms.com (opens in a new tab)
- USACO Guide – Divide & Conquer DPusaco.guide (opens in a new tab)
- USACO Guide – Divide & Conquerusaco.guide (opens in a new tab)
- CF Blog – Divide and Conquer Optimizationcodeforces.com (opens in a new tab)
- Divide and Conquer Algorithmprogramiz.com (opens in a new tab)