算法概论笔记 - 分治法

1. 将原问题分解为一组子问题，每个子问题都与原问题类型相同，但是比原问题的规模小
2. 递归求解这些子问题
3. 将子问题的求解结果恰当合并，得到原问题的解

分治算法更多地是使已经能在多项式时间内解决的问题求解得更快。

二进制乘法

假设x和y是两个n位二进制整数，我们将每个数都一分为二，每个数的左半部分和右半部分都是n/2位二进制数：

(2^{n/2}y_L + y_R) = 2^nx_Ly_L + 2^{n/2}(x_Ly_R + x_Ry_L) + x_Ry_R)

此时，T(n) = 4T(n/2) + O(n)，时间复杂度为O(n^2)

(y_L + y_R) - x_Ly_L - x_Ry_R)

这时，T(n) <= 3T(n/2 + 1) + O(n)，时间复杂度为 该二叉树至少包含有n!个叶节点（排列数目），因此这棵树的宽度至少是

其中基准v为5，指针l左侧l为比基准v小的数，而指针m左侧为不超过基准的数。当分割时遇到比基准小的数时，需要将

复根的理解如下：

插值TODO

写在最后

• 立个Flag，TODO will be done some day。
• 渣代码，且轻喷​:worried:​。