题目描述
给定一个double类型的浮点数base和int类型的整数exponent。求base的exponent次方。
保证base和exponent不同时为0
题目分析
- 题目有两种方法
1.直接使用暴力遍历来做 2.使用一种新算法:快速幂
- 暴力遍历复杂度O(n)，不提倡。这里主要讲解一下快速幂。
对于快速幂：时间复杂度O（logb） 我们已知 2^3 求 2^6,不就是 2^3 * 2^3嘛。快速幂就是这个原理。 那有同学问了遇到奇数怎么办？2 ^ 5?? 那不就是 2 * 2 ^ 4 这不就成了嘛。 所以这就是快速幂的基本思路求a ^ b 1）当b是奇数时，那么有 a^b = a * a^*(b-1) 2）当b是偶数时，那么有 a^b = a^(b/2) * a^(b/2) 举个例子？2 ^10 2^10 = 2^5 * 2^5 2^5 = 2 * 2^4 2^4 = 2^2 * 2^2 2^2 = 2^1 * 2^1 2^1 = 2 * 2^0
- 快速幂的两种表现：递归和迭代
递归
ll binaryPow(ll a, ll b, ll m){ ll ans = 1; while(b > 0){ if(b & 1){ ans = ans * a % m; } a = a * a % m; b >>= 1; } return ans; }
迭代
typedef long long ll ll binaryPow(ll a, ll b, ll m){ ll ans = 1; while(b > 0){ if(b & 1){ ans = ans * a % m; } a = a * a % m; b >>= 1; } return ans; }
题目代码
递归
public class Solution { public double Power(double base, int exponent) { int flag; if (exponent > 0) { flag = 1; } else { exponent = -exponent; flag = 0; } if (exponent == 0) { return 1; } else if (exponent % 2 == 1) { if (flag == 1) { return base * Power(base, exponent - 1); } else { return 1 / (base * Power(base, exponent - 1)); } } else { double sum = Power(base, exponent / 2); if (flag == 1) { return sum * sum; } else { return 1 / (sum * sum); } } } }
迭代
public class Solution { public double Power(double base, int exponent) { double ans = 1; if (exponent > 0) { while (exponent > 0) { if ((exponent & 1) == 1) { ans = ans * base; } base = base * base; exponent = exponent >> 1; } return ans; } else if (exponent == 0) { return 1; } else { exponent = -exponent; while (exponent > 0) { if ((exponent & 1) == 1) { ans = ans * base; } base = base * base; exponent = exponent >> 1; } return 1 / ans; } } }
