分治思想的运用

写在开始

在本文我们将接触一些运用了分治思想的算法，进一步加深对分治法的理解，同时计算一些递归式。值得注意的是，分治思想在我们之后的学习中和生活的方方面面都有非常广泛的运用，还是很值得掌握的。下面我们开始吧。

乘方问题

计算a的n次幂，我们可以直接让n个a相乘，这很显然T(n)=n，那么如何将分治法于其中呢？根据我们前文将数组一分为二的操作，我们容易直接想到我们能不能够将n也对半砍一刀呢？那么我们一次计算出a的n/2次幂，最后将两个a的n/2次幂相乘即可得到a的n次幂，看看伪代码部分。

def multiple(a,n):
    if n == 1:
        return a
    else:
        x = multiple(a,n/2)
        return x*x

这就是一个简易的乘法计算公式，但它只能处理n为1和n为偶数的情况，奇数的情况也很简单明了，我们可以把奇数先减去1化为偶数，然后再在最后乘回去即可，这里就交给聪明的读者去实现了。接下来我们来看看T(n)，显然T(n)=T(n/2)+a，这里进行递归我们只简化了问题规模为1/2，并没有划分为多个部分，所以系数就为1，b为2，然后每次递归都执行一遍x*x，时间消耗为a。当n为1的时候，T(n)=2a=Θ(1)。