碰到这么个小问题，不考虑输入为负，不考虑输出越界的情况下，求m的n次幂m^n。
1·最基本的算法，可以使用循环来搞定，时间复杂度为O(n)：
1
2
3
4
5
6
7
8
9
10
|
int pow(int m,unsigned int n)
{
int result = 1;
while(n >0)
{
result *= m;
--n;
}
return result;
}
|
2·接着考虑，如果先计算出m²，求m^n的话，只需要循环(n/2+1)次：
1
2
3
4
5
6
7
8
9
10
11
|
int pow(int m, unsigned int n)
{
int result = 1;
int tmp = m * m;
while(n > 0)
{
result *= tmp;
}
if(n % 2)
result *= m;
}
|
3·明显，如果先计算出m^4的话，时间复杂度会进一步降低，改进版代码如下，时间复杂度为O(log2n)：
1
2
3
4
5
6
7
8
9
10
11
12
13
|
int pow(int m, unsigned int n)
{
int result = 1;
int tmp = m;
while (n) {
if (n & 1)
result *= tmp;
tmp *= tmp;
n >>= 1;
}
return result;
}
|
使用递归的方式实现以上代码：
1
2
3
4
5
6
7
8
|
int (int m, unsigned int n)
{
int square_root = pow(m, n/2);
int result = square_root * square_root;
if (n & 1)
result *= m;
return result;
}
|
认知和思索，来源于生活的点点滴滴。
近期评论