Power(x, n) | 实现幂运算
Implement pow(x, n).
思路1: 分治
恰如1+2+3+…+n的解决方案,pow(x,n)也可优化拆解
二分法:x^n = x^(n/2) * x^(n/2) * x^(n%2)
时间复杂度:O(logn), 空间复杂度O(1)
1 | int power(int x, int n) { |
当然,也可以采用三分法、四分法,相应的可以降低logn的底数,但增加了x^(x%2)计算过程的复杂性,具体性能差异不明显。
思路2: 循环
最原始的实现:while(n–) pow*=x;
时间复杂度:O(n), 空间复杂度O(1)1
2
3
4
5
6
7
8int power(int x, int n) {
if(n==0)
return 1;
int res = 1;
while(n--)
res *= x;
return res;
}
总结
分治的思想,就是一个大的问题分解为更小规模的几个同类问题
。
一般此类解法与递归相配合使用,关键在于找到问题分解的方式。
Sqrt(x) | 实现开方运算
Implement int sqrt(int x).
Compute and return the square root of x.
返回x的平方根
思路
- 输入为int,返回为int
- m^2=x,求m,最简单粗暴的方式时遍历[1, x]的所有值
- 改进方案则考虑减少遍历过程的次数,二分法遍历
源码
1 | // Sqrt(x) |
总结
- x的平方根<=x/2, 因此遍历范围可缩小为[1,x/2]
- 注意避免整数溢出的操作,如(min+max)/2变更为min+(max-min)/2,mid*mid<x变更为mid<x/mid
- 特殊情况的处理:x=0,1时,直接范围x即可,理论上x不应等于0,但对于x=0的情况,这里不做异常处理,直接返回