剑指 Offer 16 - 数值的整数次方:快速幂模板
# 📃 题目描述
题目链接:剑指 Offer 16. 数值的整数次方 (opens new window)
# 🔔 解题思路
# 快速幂 + 递归
class Solution {
public double myPow(double x, int n) {
// -n 可能会超出 int 的范围 [-2^32, 2^32 - 1] (n = 2^32)
long N = n;
return N >= 0 ? quickMul(x, N) : 1.0 / quickMul(x, -N);
}
private double quickMul(double x, long N) {
if (N == 0) {
return 1.0;
}
double temp = quickMul(x, N / 2);
return (N % 2 == 0) ? temp * temp : temp * temp * x;
}
}
- 时间复杂度:O(logn),即为递归的层数
- 空间复杂度:O(logn),即为递归的层数。这是由于递归的函数调用会使用栈空间。
# 快速幂 + 迭代 TODO
# 💥 复杂度分析
- 空间复杂度:
- 时间复杂度:
🎁 公众号

各位小伙伴大家好呀,叫我小牛肉就行,目前在读东南大学硕士,上方扫码关注公众号「飞天小牛肉」,与你分享我的成长历程与技术感悟~
帮助小牛肉改善此页面 (opens new window)
Last Updated: 2023/02/16, 11:27:10