# Divide and Conquer

分治算法，将原始问题划分成 n 个规模较小，并且结构与原问题相似的子问题，递归解决这些子问题，然后合并其结果，就得到原问题的解。

分治算法与递归：分治算法是处理问题的一种思想，递归是一种编程技巧；分治算法一般都比较适合递归来实现。每一层递归都会涉及三种操作：分解、解决、合并。

适用条件：

* 原问题与分解的小问题有相同的模式。
* 原问题与子问题可以独立求解，没有相关性。
* 分解有终止条件。
* 合并操作的复杂度不能太高。

[Map-Reduce](/notes/computer-science/distributed-system/computing.md#mr) 也是利用了分治的思想。

## 例题

* [LeetCode 50：求 x 的 n 次方。](https://github.com/StoneYunZhao/algorithm/blob/master/src/main/java/com/zhaoyun/leetcode/divide/LT50.java)


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://yunzhao.gitbook.io/notes/computer-science/algorithm/divide-and-conquer.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.