menu 首页 标签 归档 视频 关于
算法-快速幂

一言加载中...

问题描述

实现 pow(x, n) ,即计算 x 的 n 次幂函数。(出自力扣)

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

看到这个题目第一眼想到的就是暴力求解。但也有些疑惑感觉有陷阱…但也没发现问题所在,就暴力一把提交了,发现当指数太大时时间就超时了…

快速幂

快速幂是一种计算一个数的n次方的算法,其时间复杂度为O(log n),暴力求解时间复杂度为O(n)。

算法描述

计算an=a * a * a * … * a,共相乘n次。根据数学公式am+n=am * an,将取幂的任务按照== 二进制表示 ==拆分成更小的任务,举个例子:
计算 313,其中13转化为二进制为(1101)2=1 * 23+1 * 22+1 * 20;
则 313=38 * 34 * 31
那么:对于xn,n=(n0 * n1 *… * nt) = n0 * 20 + n1 * 21 + … + nt * 2t
则 xn = x^(n0 20 + n1 21 + … + nt 2t)^

代码实现

递归,发现依旧超时…毕竟递归会有许多重复的操作。

public static double MyPow(double x, int n)
{
if (n == 0 || x == 1) return 1;

int nn = Math.Abs(n);

double result = MyPow(x, nn / 2) * MyPow(x, nn / 2);
if (nn % 2 == 1)
result *= x;
return n < 0 ? 1f / result : result;
}
写博客不易,请我喝杯咖啡?

评论

arrow_upward