Java习题之实现平方根(sqrt)函数

快来打我* 2024-04-20 14:28 65阅读 0赞

**目录**

前言

二分查找

牛顿迭代法

总结

--------------------

> ?博主介绍：博客名为tq02，已学C语言、JavaSE，目前学了MySQL和JavaWeb
> 
> ?学习专栏： [C语言][C] [JavaSE][] [MySQL基础][MySQL]
> 
> ?博主链接：[tq02的博客\_CSDN博客-C语言,Java,MySQL领域博主][tq02_CSDN_-C_Java_MySQL]

## 前言 ##

可使用java.lang.Math类的**sqrt(double)方法**求平方根。Math是java.lang包中的类，而Double为对象中的基本类型。但是如果不使用库函数呢？有什么办法实现平方根函数呢？

方法：**二分查找**、**牛顿迭代法、利用平方数的性质**

--------------------

## 利用平方数的性质 ##

平方数的性质：n²=1+1+2+2+....+**n-1+n-1+n**。例如4²=1+1+2+2+3+3+4=16。

1+3为2的平方，1+3+5为3的平方，

![27e83e25ee844d19b2ae0391d11737e1.png][]

也就是说每一次加一个奇数，再设置一个变量记录加了多少个奇数。

**复杂度分析：**  
时间复杂度：O(N)，每次+2的循环，为(1/2)N的时间复杂度,去掉系数，为O(N)  
空间复杂度: O(1),只使用了有限常数个变量；

int sqrt(int x) {
         if(x<=0) return 0;  //小于等于0 返回0
         int ans = 1; 
         int num = 1;
         int  i = 3;
         while(num+i<=x){
             num+=i;  
              ans ++; // 每加一个奇数，ans+1
              i += 2;
            }
            return ans;
        }

--------------------

## **二分查找** ##

如果求解一个数的平方根，这个结果肯定是在1到这个数的范围，因此我们可以使用二分查找的方法。例如求解x的平方根，思路：

1.  初始范围：1 ~ x，使用left标记1，right标记x ，取left~right的中间值，为 **middle**；
2.  当`middle*middle <= x && (middle+1)*(middle+1) > x`时，返回结果
3.  当 `middle*middle < x`时，到右半部分继续寻找，范围改成 **middle+1 ~ right**
4.  当`middle*middle > x`时，到左半部分继续寻找，范围改成 **left ~ middle+1**

注： 这种方法只能使用于整数的开跟

![b421cb97d8d3457dbfcd6863acfba9be.png][]

**复杂度分析：**  
时间复杂度:O(logn),二分查找的复杂度，每次循环减少一半  
空间复杂度;O(1)，只使用了有限常数个变量；

**代码实现：**

public int mySqrt(int x) {
        if (x <= 0) {
            return 0;
        }
        int left = 1, right = x;
        while (true) {
            int middle = (left + right) >> 1;
            if (middle <= x / middle && (middle+1) > x / (middle+1)) {
                return (int) middle;
            } else if (middle < x / middle) {
                left = middle + 1;
            } else {
                right = middle - 1;
            }
        }
    }

--------------------

## **牛顿迭代法** ##

> 牛顿迭代法简介
> 
> 假设方程 F(x)=0 在 x 附近有一个根，那么用以下迭代式子：
> 
> ![ef7d98dc60f543ee97e2dc0af44aaeee.png][]
> 
> 依次计算X1、X2、X3、...........那么序列将无限逼近方程的根。
> 
> 牛顿迭代法的原理很简单，其实是根据f(x)在x0附近的值和斜率，估计f(x)和x轴的交点，看下面的动态图：
> 
> ![70279b82104ec59a918fa70903fe1679.gif][]

![236c085a0ec249e1af148362c82e44b1.png][]

代码示例：

public class Solution {
    	public int sqrt (int x) {//牛顿迭代法
            if(x==0||x==1) return x;//题中告诉我们x的范围： 0 <= x < 2^31-1
    		long X0 = x;//使用int进行加法运算可能溢出，所以采用long型
    		long X1 = 0;//下一个迭代变量，为了方便理解，也可只使用X0
    		while(X0 > x/X0 ) {    // X0^2>x循环
    			X1=(X0+x/X0) >> 1;//由迭代公式得，采用右移1位操作代替除以2，运算更快
    			X0=X1;//把下一个迭代变量赋给X0,统一操作，方便继续处理
    		}
    		return (int)X0;//返回值类型为int,因此需要做强制类型转换
        }
    }

## 总结 ##

牛顿迭代法不像二分查找法、平方数，需要唤醒一下各位哥哥姐姐们的高中数学知识，只有这样才能理解该公式。如果唤醒失败，推荐使用二分查找法，不要逞强哦。

[C]: http://t.csdn.cn/Aynrr
[JavaSE]: http://t.csdn.cn/1Z0RB
[MySQL]: https://blog.csdn.net/m0_74097410/category_12342593.html
[tq02_CSDN_-C_Java_MySQL]: https://blog.csdn.net/m0_74097410?type=blog
[27e83e25ee844d19b2ae0391d11737e1.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/20/a0c290c9d6944d77b3235f31f5f46f1e.png
[b421cb97d8d3457dbfcd6863acfba9be.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/20/baf223163a66438195bd05ff051d14cd.png
[ef7d98dc60f543ee97e2dc0af44aaeee.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/20/59d987aeef6147fb8220715975331e19.png
[70279b82104ec59a918fa70903fe1679.gif]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/20/7381276dbaff44e48ea3117e2621b7ff.gif
[236c085a0ec249e1af148362c82e44b1.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/20/280c357848cc464ab766a30681fb7624.png