算法的学习笔记—数值的整数次方(牛客JZ16)

举报
尘觉 发表于 2024/08/12 20:15:31 2024/08/12
【摘要】 在计算机科学中,求解数值的整数次方是一个常见的数学运算问题,特别是在处理大规模计算或算法优化时。给定一个浮点数 x 和一个整数 n,我们需要求出 x 的 n 次方。虽然可以通过直接相乘 n 次来得到结果,但这种方法的时间复杂度为 O(N),在处理大数或大规模计算时效率较低。为了解决这个问题,可以采用分治思想,将计算复杂度降至 O(logN),从而提高运算效率。

😀前言
在计算机科学中,求解数值的整数次方是一个常见的数学运算问题,特别是在处理大规模计算或算法优化时。给定一个浮点数 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。

image.png

因为 (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),大大提高了计算效率。该方法通过递归将问题规模不断缩小,并通过合并子问题的解得到最终结果。同时,考虑到次方数为负的情况,我们也通过判断负数的逻辑处理了这种特殊情况。该算法不仅高效,而且在处理大规模数据时表现尤为突出。

【版权声明】本文为华为云社区用户原创内容,转载时必须标注文章的来源(华为云社区)、文章链接、文章作者等基本信息, 否则作者和本社区有权追究责任。如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@huaweicloud.com
  • 点赞
  • 收藏
  • 关注作者

评论(0

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。