在m和n都属于正数，并且m的n次方不超过LONG_MAX的情况下，如何求出m的n次方呢？一般都会想到用一个循环，如下

long result = 1;

for (int i = 0; i < n; i++)

result * = m;

result即为所求，算法复杂度O(n)。这样也能工作，但是当m和n变大时，效率会相当低下，如何优化呢？考虑2的4次方的情况，其实就是4个2相乘法；有没有看出撒问题呢？是的，重复计算！前二个2相乘的结果可以直接用，后面两个2的相乘不用再计算，即是

2X2X2X2 = 4X4

考虑2的5次方，即5个2相乘的情况，同样的道理

2X2X2X2X2 = 4X4X2

所呈现出来的规律即是

m的n次方，在n为偶数时，可以变成 m的n/2次方的平方；在n为奇数时，则有n - 1为偶数，则变成m的(n-1)/2次方的平方再乘以m, 从n变成n/2，问题规模变小，中间计算结果可重复利用，可用递归解决，其算法复杂度变成O(logn)。具体代码见下：

 

 

 

 

运行结果如下