首页 > 代码库 > 幂运算
幂运算
如果我们要计算一个数X的N次幂，那么很直接地，我们可以写出以下代码：
1 int 2 Power(int base, int pow) 3 { 4 int result; 5 result = 1; 6 7 while (pow > 0) { 8 result *= base; 9 pow--;10 }11 return result;12 }
上述程序的复杂度为O(N)。但其实由于从数学的角度来看，如果N是偶数，那么XN = XN/2 * XN/2 。如果N是奇数，那么 XN = XN/2 * XN/2 * X。
所以我们可以有以下代码，简化上述程序的运算：
1 int 2 Power(int base, int pow) 3 { 4 if (pow == 0) { 5 return 1; 6 } 7 if (pow == 1) { 8 return base; 9 }10 if (pow % 2 == 0) {11 return Power(base*base, pow/2);12 } else {13 return Power(base*base, pow/2) * base;14 }15 }
在这种情况下，我们只需要O(logN)的时间就可以完成计算。
幂运算
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。