分治法——大数相乘（算法001）

两个长为n-bit的数x和y相乘。我们可以将数分为长为n/2-bit的前后两部分，分别相乘。
x * y
= (2^n/2x_L + x_R) * (2^n/2y_L + y_R)
= 2ⁿx_Ly_L + 2^n/2(x_Ly_R + x_Ry_L) + x_Ry_R
= 2ⁿx_Ly_L + 2^n/2((x_L+x_R)(y_L+y_R) - x_Ly_L - x_Ry_R) + x_Ry_R
公式如上，
x_L，y_L，x_R，y_R，(x_L+x_R)，(y_L+y_R)都只有n/2-bit，2个长为n-bit的数相城，简化成了6个n/2-bit的数简单的相乘相加减，大大的提升了计算的效率。
我们可以就这样把它一直分解下去，如：

成功将大规模问题分解成了若干个小规模问题。
算法分析：

• 树一共有log₂n层；
• 在第k层上，总共产生3^k个子问题，每个子问题的输入大小是n/2^k，即是两个n/2^k-bit数相乘；
• 在第k层上，算法需要线性时间将子问题的解组合为上一层问题的解，因此，该层算法的执行时间为3^k*O(n/2^k)=(3/2)^k*O(n)；
• 在顶层，k=0，执行时间为O(n)；
• 在最后一层，k=log₂n，执行时间为O(3^log~2~n)；
• 在每层上算法执行时间呈指数上升，从O(n)到O(3^log~2~n)，所有层相加，算法执行时间为O(3^log~2~n)，约等于O(n^1.59)。