算法的学习笔记—数值的整数次方(牛客JZ16)
😀前言
在计算机科学中,求解数值的整数次方是一个常见的数学运算问题,特别是在处理大规模计算或算法优化时。给定一个浮点数 x 和一个整数 n,我们需要求出 x 的 n 次方。虽然可以通过直接相乘 n 次来得到结果,但这种方法的时间复杂度为 O(N),在处理大数或大规模计算时效率较低。为了解决这个问题,可以采用分治思想,将计算复杂度降至 O(logN),从而提高运算效率。
🤩数值的整数次方
🥰题目链接
🤗题目描述
给定一个 double 类型的浮点数 x和 int 类型的整数 n,求 x 的 n 次方。
题目描述
给定一个 double 类型的浮点数 x和 int 类型的整数 n,求 x 的 n 次方。
注意:
1.保证base和exponent不同时为0。
2.不得使用库函数,同时不需要考虑大数问题
3.有特殊判题,不用考虑小数点后面0的位数。
数据范围: ∣base∣≤100 , ∣exponent∣≤100 ,保证最终结果一定满足 ∣val∣≤10^4^
进阶:空间复杂度 O(1) ,时间复杂度 O(n)
🤔示例1
输入:2.00000,3
返回值:8.00000
🤔示例2
输入:2.10000,3
返回值:9.26100
🤔示例3
输入:2.00000,-2
返回值:0.25000
说明:2的-2次方等于1/4=0.25
😁解题思路
最直观的解法是将 x 重复乘 n 次,x*x*x…*x,那么时间复杂度为 O(N)。因为乘法是可交换的,所以可以将上述操作拆开成两半 (x*x…*x)* (x*x…*x),两半的计算是一样的,因此只需要计算一次。而且对于新拆开的计算,又可以继续拆开。这就是分治思想,将原问题的规模拆成多个规模较小的子问题,最后子问题的解合并起来。
本题中子问题是 xn/2,在将子问题合并时将子问题的解乘于自身相乘即可。但如果 n 不为偶数,那么拆成两半还会剩下一个 x,在将子问题合并时还需要需要多乘于一个 x。
因为 (x*x)n/2 可以通过递归求解,并且每次递归 n 都减小一半,因此整个算法的时间复杂度为 O(logN)。
public double Power(double x, int n) {
boolean isNegative = false;
if (n < 0) {
n = -n;
isNegative = true;
}
double res = pow(x, n);
return isNegative ? 1 / res : res;
}
private double pow(double x, int n) {
if (n == 0) return 1;
if (n == 1) return x;
double res = pow(x, n / 2);
res = res * res;
if (n % 2 != 0) res *= x;
return res;
}
😄总结
通过利用分治法求解数值的整数次方问题,我们成功地将计算复杂度从 O(N) 降至 O(logN),大大提高了计算效率。该方法通过递归将问题规模不断缩小,并通过合并子问题的解得到最终结果。同时,考虑到次方数为负的情况,我们也通过判断负数的逻辑处理了这种特殊情况。该算法不仅高效,而且在处理大规模数据时表现尤为突出。
- 点赞
- 收藏
- 关注作者
评论(0)