门户网站开发介绍,东营房产网信息网,青岛高端模板建站,jsp网站开发软件哪个好文章目录 写在前面Tag题目来源题目解读解题思路方法一#xff1a;快速幂-递归方法二#xff1a;快速幂-迭代 其他语言python3 写在最后 写在前面 本专栏专注于分析与讲解【面试经典150】算法#xff0c;两到三天更新一篇文章#xff0c;欢迎催更…… 专栏内容以分析题目为主… 文章目录 写在前面Tag题目来源题目解读解题思路方法一快速幂-递归方法二快速幂-迭代 其他语言python3 写在最后 写在前面 本专栏专注于分析与讲解【面试经典150】算法两到三天更新一篇文章欢迎催更…… 专栏内容以分析题目为主并附带一些对于本题涉及到的数据结构等内容进行回顾与总结文章结构大致如下部分内容会有增删 Tag介绍本题牵涉到的知识点、数据结构题目来源贴上题目的链接方便大家查找题目并完成练习题目解读复述题目确保自己真的理解题目意思并强调一些题目重点信息解题思路介绍一些解题思路每种解题思路包括思路讲解、实现代码以及复杂度分析知识回忆针对今天介绍的题目中的重点内容、数据结构进行回顾总结。 Tag
【快速幂】 题目来源
50. Pow(x, n) 题目解读
计算一个数的整数次幂。 解题思路
计算一个数的整数次幂有朴素的方法和二分的方法朴素的方法就是一个一个的乘起来时间复杂度为 O ( n ) O(n) O(n) n n n 指的是幂指数。接下来要介绍的是二分法即快速幂有递归和迭代两种解法。建议读者掌握快速幂的方法该方法是一些题目计算的一个重要工具。
方法一快速幂-递归
写递归代码的一个重要思想坚信自己写的递归就是对的可以直接调用。用快速幂求解一个数的整数次幂是一种二分的递归比如我们要计算 x n x^n xn 时
我们可以先递归的计算 y x ⌊ n / 2 ⌋ y x^{\lfloor{n / 2} \rfloor} yx⌊n/2⌋如果 n 是偶数那么 x n y 2 x^ny^2 xny2如果 n n n 是奇数那么 x n y 2 × x x^ny^2 \times x xny2×x;递归的边界递归出口为 n 0因为任意数的 0 次方均为 1。
实现代码
class Solution {
public:double quickMul(double x, long long N) {if (N 0) return 1.0;double y quickMul(x, N/2);return N 1 ? y * y * x : y * y;}double myPow(double x, int n) {long long N n;return N 0 ? quickMul(x, N) : 1.0 / quickMul(x, -N);}
};复杂度分析
时间复杂度 O ( l o g n ) O(logn) O(logn) n n n 为幂指数。因为每次递归都会使指数减少一半因此递归的层数为 O ( l o g n ) O(logn) O(logn)时间复杂度也为 O ( l o g n ) O(logn) O(logn)。
空间复杂度 O ( l o g n ) O(logn) O(logn)。
方法二快速幂-迭代
在完全理解了递归的思想后会发现递归真简单但是完全理解递归之前还是觉得迭代简单容易理解。现在就来看看迭代解法。
我们依旧是使用二分来计算幂
如果指数为奇数则累乘答案即 res * x然后更新 x * x最后返回 res 即可。
实现代码
class Solution {
public:double quickMul(double x, long long n) {double res 1.0;for (; n; n / 2) {if (n 1) {res * x;}x * x;}return res;}double myPow(double x, int n) {long long N n;return N 0 ? quickMul(x, N) : 1.0 / quickMul(x, -N);}
};复杂度分析
时间复杂度 O ( l o g n ) O(logn) O(logn) n n n 为幂指数。
空间复杂度 O ( 1 ) O(1) O(1)。 其他语言
python3
在 Python 中可以使用内置的 pow 函数来进行快速幂的计算。pow 函数的签名如下
pow(x, y, zNone, /)其中x 为底数y 为指数z 为模数如果指定了模数则返回 x**y % z。这个函数的时间复杂度较低因为它采用了快速幂的算法。
以下是一个示例
# 计算 2 的 10 次方
result pow(2, 10)# 输出结果
print(result)上述代码会输出 1024即 2 的 10 次方的结果。在这个例子中pow 函数的参数分别为底数、指数没有指定模数。 写在最后
如果文章内容有任何错误或者您对文章有任何疑问欢迎私信博主或者在评论区指出 。
如果大家有更优的时间、空间复杂度方法欢迎评论区交流。
最后感谢您的阅读如果感到有所收获的话可以给博主点一个 哦。
