国产探花免费观看_亚洲丰满少妇自慰呻吟_97日韩有码在线_资源在线日韩欧美_一区二区精品毛片,辰东完美世界有声小说,欢乐颂第一季,yy玄幻小说排行榜完本

首頁 > 學院 > 開發設計 > 正文

指定誤差求開平方之不同算法實現之間的效率比較(java實現)

2019-11-14 11:47:01
字體:
來源:轉載
供稿:網友

本文通過比較對數字指定誤差的求開平方不同算法實現之間的效率比較,來使程序入門者對不同算法的性能差距有直觀的印象,并且對算法的作用有深刻的體會。

算法一(暴力遍歷法):

	/**	 * 求開方	 * @param source 被開方數,大于等于0	 * @param deviation 誤差范圍	 * @return	 */	public static double sqrt(double source,double deviation) {				if(source < 0 || deviation <0) {			throw new RuntimeException("don't transmit negtive");		}		long count = 1;//統計循環執行次數		double result = 0;		while ((result + 1) * (result + 1) < source) {			count++;			result++;		}		while ((result + deviation) * (result + deviation) < source ) {			count++;			result += deviation;		}		System.out.PRintln("sqrt total count:" + count);		return result;	}

本算法是將計算結果從0開始一點一點增加并進行試探,直到接近真實結果誤差范圍內。

算法二(步長調整法):

/**	 * 求開方 優化,步長調整	 * @param source 被開方數,大于等于0	 * @param deviation 誤差范圍	 * @return	 */	public static double sqrt1(double source,double deviation) {				if(source < 0 || deviation <0) {			throw new RuntimeException("don't transmit negtive");		}		long count = 1;//統計循環執行次數		double result = 0;		int stepI = 2;		double stepD = deviation;		long stepCount = 1;		while ((result + 1) * (result + 1) < source) {			count++;			stepCount++;			if(stepCount%3==0){  //加快結果累計,調整步長				if((result + stepI) * (result + stepI) < source) {					result += stepI;					stepI++;					continue;				} else {					stepI--;				}			}			result++;		}		stepCount = 0;		while ((result + deviation) * (result + deviation) < source ) {			count++;			stepCount++;			if(stepCount%3==0){  //加快結果累計,調整步長				if((result + stepD) * (result + stepD) < source) {					result += stepD;					stepD+=deviation;					continue;				} else {					stepD-=deviation;				}			}			result += deviation;		}		System.out.println("sqrt1 total count :" + count);		return result;	}

本算法每當執行循環三次時調整一次步長,讀者可以自行定制更加高效的調整步長策略。

算法三(二分法):

	/**	 * 求開方 優化,二分法	 * 該方法效率明顯比前兩個方法快的多	 * @param source 被開方數,大于等于0	 * @param deviation 誤差范圍	 * @return	 */	public static double sqrt2(double source,double deviation) {				if(source < 0 || deviation <0) {			throw new RuntimeException("don't transmit negtive");		}		long count = 1;//統計循環執行次數		double result = 0;				double head = source;		double tail = 0;		while(true) {			count++;			if(((head+tail)/2) * ((head+tail)/2) < source) {				tail = (head+tail)/2;			} else {				head = (head+tail)/2;			}			result = (head+tail)/2;			if((result + deviation)*(result + deviation) >= source &&					(result - deviation)*(result - deviation) <= source) {				break;			}		}		System.out.println("sqrt2 total count:" + count);		return result;	}

本算法為典型的二分法,算法的原理如下:將0和source分別作為結果的初始下界和上界,將下界和上界的平均值與真實結果比較并調整結果的下界或者上界,直至結果位于真實結果的誤差范圍內。

上面已經給出了算法的實現,算法可能的難點是怎么判斷算出的值是否在誤差范圍內,讀者需要注意這點。下面通過幾組數據簡單的比較一下不同算法實現之間的效率差別:

                                                                      

上圖中,我們測試了三組數據,從標紅的數據可以看出,算法二明顯優于算法一,而算法三明顯優于算法二。當執行第三組數據時,算法一甚至要等一小會兒才能執行完,而算法三卻馬上就能得到結果,而且算法三隨著問題規模的擴大執行次數卻增長很慢,而這只是簡單的幾行代碼改進的結果。從這個算法問題中我們可以看到不同算法之間效率的巨大差距,由此不難體會在許多算法應用場合下算法巨大的威力。


發表評論 共有條評論
用戶名: 密碼:
驗證碼: 匿名發表
主站蜘蛛池模板: 南郑县| 策勒县| 襄汾县| 亚东县| 邮箱| 连山| 城口县| 榆林市| 湾仔区| 西宁市| 永顺县| 抚州市| 丹东市| 车险| 那坡县| 邵东县| 华蓥市| 宁陵县| 张家港市| 元朗区| 砀山县| 民勤县| 江西省| 达州市| 巍山| 岢岚县| 沭阳县| 化州市| 买车| 楚雄市| 凭祥市| 浪卡子县| 天气| 濮阳市| 夏津县| 文安县| 郴州市| 赤城县| 叙永县| 长寿区| 礼泉县|