算法思路:
1. 如果是奇数幂,x * p(x,n-1)
2.如果是偶数幂,p(x , n/2) * p (x, n/2)
3. 如果n=0 ,返回1
时间复杂度 : O(logN)
具体实现:
- function fastPow(x,n){
- if(n == 0){
- return 1;
- }
- else if(n % 2 == 1){
- return fastPow(x,n-1) * x;
- }
- else{
- var r = fastPow(x,n/2);
- return r * r;
- }
- }
- console.log(fastPow(2,100));
来源: http://www.phpxs.com/code/1003651/