在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)。具体代码见下：
运行结果如下
文章来源于互联网，侵权请联系删除。如若转载，请注明出处：https://www.xiaopangyu.com/zixun/26383.html
