☆打卡算法☆LeetCode 50、Pow(x, n) 算法解析

推荐阅读

• CSDN主页
• GitHub开源地址
• Unity3D插件分享
• 简书地址
• 我的个人博客
• QQ群：1040082875

大家好，我是小魔龙，Unity3D软件工程师，VR、AR，虚拟仿真方向，不定时更新软件开发技巧，生活感悟，觉得有用记得一键三连哦。

一、题目

1、算法题目

“实现函数，计算x的n次幂。”

题目链接：

来源：力扣（LeetCode）

链接：50. Pow(x, n) - 力扣（LeetCode） (leetcode-cn.com)

2、题目描述

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

示例 1：
输入： x = 2.00000, n = 10
输出： 1024.00000

示例 2：
输入： x = 2.10000, n = 3
输出： 9.26100

二、解题

1、思路分析

这道题可以使用快速幂+递归的方法解题。

快速幂算法，本质就是分治算法，将大问题分解成小问题，然后递归解决。

快速幂算法：

比如要计算x⁸，可以按照x → x² → x⁴ → x⁸的顺序，从x开始，每次将上一次的结果进行平方，3次后就可以得到x⁸的结果，而不需要对x乘8次x。

如果幂是偶数，比如x⁹，可以按照x → x² → x⁴ → x⁹的顺序，这些步骤中，还是按照将上一次结果平方，而在x⁴ → x⁹的步骤中，需要将上一个结果进行平方，还需要额外乘一个x。

综上所述，可以推到出规律，如果要计算xⁿ，首先判断n的奇偶：

• n为偶数，那么xⁿ=yⁿ
• n为奇数，那么xⁿ=yⁿ * x

接着就可以递归地得到结果了。

2、代码实现

代码参考：

public class Solution {
    //递归
    public double MyPow(double x, int n) {
        return (n >= 0) ? res(x, n) : 1 / res(x, n);
    }
    private double res(double x, int n)
    {
        if(n == 0)
            return 1;
        double y = res(x, n / 2);
        return (n % 2 == 0) ? y * y :y * y * x;
    }
}

3、时间复杂度

时间复杂度 ： O(log n)

其中n为遍历的层数。

空间复杂度： O(log n)

其中n为遍历的层数。

三、总结

这道题还有更秀的一行解题法：

public class Solution {
    public double MyPow(double x, int n) {
        return Math.Pow(x,n);
    }
}

是不是秀的头皮发麻。。。