数据结构与算法-快速幂
2020-09-05 17:14:46 # 数据结构与算法

什么是快速幂算法呢?

这是在 LeetCode 上遇见的一道题目,50. Pow(x, n),题目描述如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
实现 pow(x, n) ,即计算 x 的 n 次幂函数。

示例 1:

输入: 2.00000, 10
输出: 1024.00000
示例 2:

输入: 2.10000, 3
输出: 9.26100
示例 3:

输入: 2.00000, -2
输出: 0.25000
解释: 2-2 = 1/22 = 1/4 = 0.25
说明:

-100.0 < x < 100.0
n 是 32 位有符号整数,其数值范围是 [−231, 231 − 1] 。

一看这题目不难呀,直接一个循环累积相乘(xxx*……..x),轻松愉快的编写完代码,提交。

  • 第一次提交代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
impl Solution {
pub fn my_pow(x: f64, n: i32) -> f64 {
if x == 1.0 || n == 0 {
return 1.0;
}

let mut result = 1.00;
let mut base = if n > 0 { x } else { 1.0 / x };
let mut power = (n as i64).abs();

while power != 0 {
result = result * base;
power -= 1;
}

result
}
}

不出意外,等来了一个 超出时间限制,这个方案的时间复杂度为 O(n) , 那么我们有没有更快的办法呢? 当然是有的,就是下面要说的快速幂。

举个例子: 十进制的数11 可以换算成二进制的数 , 从左到右, 这些1分别代表十进制中的 8,2,1, 所以 a^11=a^(8+2+1)=(a^8)x(a^2)x(a^1).
好的, 有了上面的例子帮助理解, 下面我们直接叙述快速幂算法的原理:

  • 如果将 a 自乘一次, 那么会得到 a^2, 再自乘一次, 会得到 a^4, a^8, 自乘 n 次, 我们会得到 a^2n.

第二次提交–快速幂实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
impl Solution {
pub fn my_pow(x: f64, n: i32) -> f64 {
if x == 1.0 || n == 0 {
return 1.0;
}

let mut result = 1.00;
let mut base = if n > 0 { x } else { 1.0 / x };
let mut power = (n as i64).abs();

while power > 0 {
if power % 2 == 1 {
result *= base;
}

power = power / 2;
base *= base;
}

result
}
}

第三次提交–再优化

快速幂已经挺快了,但是我们可以通过位运算,继续优化一下。

改进 power%2==1power & 1 == 1

power%2==1 可以用更快的位运算来代替,例如:power&1。因为如果power 为偶数,则其二进制表示的最后一位一定是 0;如果 power 是奇数,则其二进制表示的最后一位一定是1。将他们分别与 1 的二进制做 & 运算,得到的就是 power 二进制最后一位的数字了,是 0 则为偶数,是1则为奇数。因此奇偶数的判断就可以用位运算来替换了。等价于 power & 1 == 1

改进 power = power / 2power >>= 1

对于 power=power/2 来说,也可以用更快的位运算进行替代,我们只要把 power 的二进制表示向右移动 1 位就是原来数的一半,就是除以 2 操作。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
impl Solution {
pub fn my_pow(x: f64, n: i32) -> f64 {
if x == 1.0 || n == 0 {
return 1.0;
}

let mut result = 1.00;
let mut base = if n > 0 { x } else { 1.0 / x };
let mut power = (n as i64).abs();

while power > 0 {
if power & 1 == 1 {
result *= base;
}

power >>= 1;
base *= base;
}

result
}
}