算法-快速幂｜默然的博客

问题描述

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

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

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

快速幂

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

算法描述

计算a^n^=a * a * a * … * a,共相乘n次。根据数学公式a^m+n^=a^m^ * a^n^,将取幂的任务按照== 二进制表示 ==拆分成更小的任务，举个例子：
计算 3^13^，其中13转化为二进制为(1101)2=1 * 2^3^+1 * 2^2^+1 * 2^0^;
则 3^13^=3^8^ * 3^4^ * 3^1^
那么：对于x^n^，n=(n^0^ * n^1^ *… * n^t^) = n0 * 2^0^ + n1 * 2^1^ + … + nt * 2^t^
则 x^n^ = x^(n0 2^0^ + n1 2^1^ + … + nt 2^t^)^

代码实现

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

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;
}

相关阅读

• 分治算法解决问题再回顾
• 算法-从第一个元素开始，计算累和的最大值