6.12 如何计算一个数的n次方
【出自WR面试题】
难度系数：★★★☆☆ 被考察系数：★★★★☆
题目描述：
给定一个数d和n，如何计算d的n次方？例如：d=2，n=3，d的n次方为2^3=8。
分析与解答：
方法一：蛮力法
可以把n的取值分为如下几种情况：
（1）n=0，那么计算结果肯定为1。
（2）n=1，计算结果肯定为d。
（3）n＞0，计算方法为：初始化计算结果result=1，然后对result执行n次乘以d的操作，得到的结果就是d的n次方。
（4）n＜0，计算方法为：初始化计算结果result=1，然后对result执行|n|次除以d的操作，得到的结果就是d的n次方。
以2的3次方为例，首先初始化result=1，接着对result执行三次乘以2的操作：result=result*2=1*2=2，result=result*2=2*2=4，result=result*2=4*2=8，因此，2的3次方等于8。根据这个思路给出实现代码如下：
程序的运行结果如下：
8
-8
0.125
算法性能分析：
这种方法的时间复杂度为O（n），需要注意的是，当n非常大的时候，这种方法的效率是非常低的。
方法二：递归法
由于方法一没有充分利用中间的计算结果，因此，算法效率还有很大的提升余地。例如在计算2的100次方的时候，假如已经计算出了2的50次方的值tmp=2^50，就没必要对tmp再乘以50次2，可以直接利用tmp*tmp就得到了2^100的值。可以利用这个特点给出递归实现方法如下：
（1）n=0，那么计算结果肯定为1。
（2）n=1，计算结果肯定为d。
（3）n＞0，首先计算2^（n/2）的值tmp，如果n为奇数，那么计算结果result=tmp*tmp*d，如果n为偶数，那么计算结果result=tmp*tmp。
（4）n＜0，首先计算2^（|n/2|）的值tmp，如果n为奇数，那么计算结果result=1/（tmp*tmp*d），如果n为偶数，那么计算结果result=1/（tmp*tmp）。
根据以上思路实现代码如下：
算法性能分析：
这种方法的时间复杂度为O（（log2n）。