都昌县建设局网站,做网站的名字大全,wordpress开发前台登录插件,wap是什么意思啊摘要
剑指 Offer 16. 数值的整数次方
本题的方法被称为快速幂算法#xff0c;有递归和迭代两个版本。这篇题解会从递归版本的开始讲起#xff0c;再逐步引出迭代的版本。当指数n为负数时#xff0c;我们可以计算 x^(-n)再取倒数得到结果#xff0c;因此我们只需要考虑n为…摘要
剑指 Offer 16. 数值的整数次方
本题的方法被称为快速幂算法有递归和迭代两个版本。这篇题解会从递归版本的开始讲起再逐步引出迭代的版本。当指数n为负数时我们可以计算 x^(-n)再取倒数得到结果因此我们只需要考虑n为自然数的情况。
一快速幂 递归
快速幂算法的本质是分治算法。举个例子如果我们要计算x^64我们可以按照: 的顺序从x开始每次直接把上一次的结果进行平方计算6次就可以得到 x^(64)的值而不需要对 x乘 63次x。再举一个例子如果我们要计算 x^77我们可以按照 的顺序在 x→x^2x2→x^4x19→x^38 这些步骤中我们直接把上一次的结果进行平方而在 x4→x^9x9→x19x38→x77这些步骤中把上一次的结果进行平方后还要额外乘一个 x。直接从左到右进行推导看上去很困难因为在每一步中我们不知道在将上一次的结果平方之后还需不需要额外乘 xx。但如果我们从右往左看分治的思想就十分明显了
当我们要计算 x^n时我们可以先递归地计算出 yx⌊n/2⌋其中⌊a⌋表示对a进行下取整根据递归计算的结果如果 n为偶数那么 x^ny^2如果n为奇数那么 x^ny^2×x递归的边界为n0任意数的0次方均为1。
由于每次递归都会使得指数减少一半因此递归的层数为 O(logn)算法可以在很快的时间内得到结果。
class Solution {public double myPow(double x, int n) {long N n;return N 0 ? quickMul(x, N) : 1.0 / quickMul(x, -N);}public double quickMul(double x, long N) {if (N 0) {return 1.0;}double y quickMul(x, N / 2);return N % 2 0 ? y * y : y * y * x;}
}
复杂度分析
时间复杂度O(logn)即为递归的层数。空间复杂度O(logn)即为递归的层数。这是由于递归的函数调用会使用栈空间。
二、快速幂 迭代
由于递归需要使用额外的栈空间我们试着将递归转写为迭代。在方法一中我们也提到过从左到右进行推导是不容易的因为我们不知道是否需要额外乘x。但我们不妨找一找规律看看哪些地方额外乘了x并且它们对答案产生了什么影响。 class Solution {public double myPow(double x, int n) {long N n;return N 0 ? quickMul(x, N) : 1.0 / quickMul(x, -N);}public double quickMul(double x, long N) {double ans 1.0;// 贡献的初始值为 xdouble x_contribute x;// 在对 N 进行二进制拆分的同时计算答案while (N 0) {if (N % 2 1) {// 如果 N 二进制表示的最低位为 1那么需要计入贡献ans * x_contribute;}// 将贡献不断地平方x_contribute * x_contribute;// 舍弃 N 二进制表示的最低位这样我们每次只要判断最低位即可N / 2;}return ans;}
}
复杂度分析 时间复杂度O(logn)即为对n进行二进制拆分的时间复杂度。 空间复杂度O(1)。
博文参考
《leetcode》
