分治

分治

• 将问题划分为若干个子问题，规模相当。问题形式不变。
• 综合子问题的解，得到原问题的解。

例：

• 时间复杂度：几何级数，底层为 $O(n)$

$$\begin{array}{rl}& T(n)=2\cdot T\left(\frac{n}{2}\right)+O(1)\\ & T(1)=O(1)\\ & T(n)=O(n)\end{array}$$

• 空间复杂度：空间占用量最大的时刻，$O(\log n)$