快捷導(dǎo)航

Java練習(xí)題之實(shí)現(xiàn)平方根(sqrt)函數(shù)

更新時(shí)間：2023年07月14日 10:45:31 作者：tq02

這篇文章主要介紹了Java練習(xí)題之實(shí)現(xiàn)平方根(sqrt)函數(shù)的相關(guān)資料,平方根是一個(gè)數(shù)學(xué)概念,表示一個(gè)數(shù)的正平方根,文中通過代碼和圖文介紹的非常詳細(xì),需要的朋友可以參考下

前言

可使用java.lang.Math類的sqrt(double)方法求平方根。Math是java.lang包中的類，而Double為對象中的基本類型。但是如果不使用庫函數(shù)呢？有什么辦法實(shí)現(xiàn)平方根函數(shù)呢？

方法：二分查找、牛頓迭代法、利用平方數(shù)的性質(zhì)

利用平方數(shù)的性質(zhì)

平方數(shù)的性質(zhì)：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的平方，

也就是說每一次加一個(gè)奇數(shù)，再設(shè)置一個(gè)變量記錄加了多少個(gè)奇數(shù)。

復(fù)雜度分析：

時(shí)間復(fù)雜度：O(N)，每次+2的循環(huán)，為(1/2)N的時(shí)間復(fù)雜度,去掉系數(shù)，為O(N)

空間復(fù)雜度: O(1),只使用了有限常數(shù)個(gè)變量；

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 ++; // 每加一個(gè)奇數(shù)，ans+1
          i += 2;
        }
        return ans;
    }

二分查找

如果求解一個(gè)數(shù)的平方根，這個(gè)結(jié)果肯定是在1到這個(gè)數(shù)的范圍，因此我們可以使用二分查找的方法。例如求解x的平方根，思路：

初始范圍：1 ~ x，使用left標(biāo)記1，right標(biāo)記x ，取left~right的中間值，為 middle；
當(dāng)middle*middle <= x && (middle+1)*(middle+1) > x時(shí)，返回結(jié)果
當(dāng) middle*middle < x時(shí)，到右半部分繼續(xù)尋找，范圍改成 middle+1 ~ right
當(dāng)middle*middle > x時(shí)，到左半部分繼續(xù)尋找，范圍改成 left ~ middle+1

注：這種方法只能使用于整數(shù)的開跟

復(fù)雜度分析：

時(shí)間復(fù)雜度:O(logn),二分查找的復(fù)雜度，每次循環(huán)減少一半

空間復(fù)雜度;O(1)，只使用了有限常數(shù)個(gè)變量；

代碼實(shí)現(xiàn)：

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;
        }
    }
}

牛頓迭代法

牛頓迭代法簡介

假設(shè)方程 F(x)=0 在 x 附近有一個(gè)根，那么用以下迭代式子：

依次計(jì)算X1、X2、X3、...........那么序列將無限逼近方程的根。

牛頓迭代法的原理很簡單，其實(shí)是根據(jù)f(x)在x0附近的值和斜率，估計(jì)f(x)和x軸的交點(diǎn)，看下面的動(dòng)態(tài)圖：

代碼示例：

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進(jìn)行加法運(yùn)算可能溢出，所以采用long型
		long X1 = 0;//下一個(gè)迭代變量，為了方便理解，也可只使用X0
		while(X0 > x/X0 ) {    // X0^2>x循環(huán)
			X1=(X0+x/X0) >> 1;//由迭代公式得，采用右移1位操作代替除以2，運(yùn)算更快
			X0=X1;//把下一個(gè)迭代變量賦給X0,統(tǒng)一操作，方便繼續(xù)處理
		}
		return (int)X0;//返回值類型為int,因此需要做強(qiáng)制類型轉(zhuǎn)換
    }
}