數據結構java版之大O表示法

wudengzan 發布于2019-08-16 15:09 / 2964人閱讀

摘要：二分查找法要查找的數數組長度設定的數組花了多少次找到最小值最大值當前猜的值打印猜的每個數找到了花了次如果猜的數大于選定的數，則把設為猜的數，否則把設為猜的數請輸入大于等于的正整數且查找的數不能大于數組里最大的數調用方法執行結果找到了花了次

大O表示法使用大寫字母O，可以認為其含義為"order of"（大約是）。我們可以使用大O法來描述線性查找使用了O(N)級時間，二分查找使用了O(log N)級時間，向一個無序數組中插入使用了O(1)，或常數級時間。
下面的圖總結了算法的運行時間：

通過圖我們可以比較不同的大O值，O(1)是優秀，O(logN)是良好，O(N)是還可以，O(N^2)則很差了，比如冒泡排序。
下面我們通過例子來看一下二分查找法。就是我們玩過的游戲猜數字，設定一個數組大小，一個人心里想一個數，讓另外一個人來猜。每次告訴他猜大了還是小了，直到猜中為止。看花了多少步。

/**
* 二分查找法
* @param search 要查找的數
* @param total 數組長度
*/
public void compute(int search,int total){
//設定的數組
int[] num;
if(total > 0 && search <= total && search >= 0){
num = new int[total];
for (int i = 0 ; i < total; i++){
num[i] = i;
}
//花了多少次找到
int sum = 0;
//最小值
int min = 0 ;
//最大值
int max = total;
//當前猜的值
int current;
while (true){
sum ++ ;
current = (min + max) / 2;
//打印猜的每個數
System.out.println(current);
if(num[current] == search){
System.out.println("找到了,花了" + sum + "次");
return;
}else{
//如果猜的數大于選定的數，則把max設為猜的數，否則把min設為猜的數
if(num[current] > search){
max = num[current] ;
}else{
min = num[current];
}
}

}
}else {
System.out.println("請輸入大于等于0的正整數且查找的數不能大于數組里最大的數");
}
}

調用方法：

compute(3,100)
執行結果：

50
25
12
6
3
找到了,花了5次

GPU云服務器云服務器 java表示 java 表示概率 java乘積怎么表示 java多個空格表示

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/73301.html

數據結構java版之冒泡排序及優化

摘要：外層循環讓內層循環繼續排沒有排序過的數組，排序過的不用再排。那么優化后的算法能快多少呢。我們都以數組長度為來計算傳統冒泡排序步，優化后的冒泡排序步。因為優化后的冒泡排序，每排完一次，最后一個數已經是最大的，就不需要再比較了。冒泡排序的時間用大O表示法是O(N^2). 傳統的冒泡排序： /** * @param total 要排序的數組長度 */ public void sort(in...

xiaoqibTn 2019-08-16 15:09 評論0 收藏0
【Vue原理】依賴收集 - 源碼版之基本數據類型

摘要：當東西發售時，就會打你的電話通知你，讓你來領取完成更新。其中涉及的幾個步驟，按上面的例子來轉化一下你買東西，就是你要使用數據你把電話給老板，電話就是你的，用于通知老板記下電話在電話本，就是把保存在中。剩下的步驟屬于依賴更新寫文章不容易，點個贊唄兄弟專注 Vue 源碼分享，文章分為白話版和源碼版，白話版助于理解工作原理，源碼版助于了解內部詳情，讓我們一起學習吧研究基于 Vue版本【...

VincentFF 2019-08-26 14:00 評論0 收藏0
【Vue原理】Slot - 源碼版之普通插槽

摘要：我們都知道分為普通和作用域，兩個內容都很多，所以分兩部分進行講述。今天講的是普通其實普通，表示默認和具名，只是他們的處理方式都差不多，就只是是否有自定義名字而已，所以，表示一種類型。寫文章不容易，點個贊唄兄弟專注 Vue 源碼分享，文章分為白話版和源碼版，白話版助于理解工作原理，源碼版助于了解內部詳情，讓我們一起學習吧研究基于 Vue版本【2.5.17】如果你覺得排版難看，請...

lansheng228 2019-08-23 18:28 評論0 收藏0
Android開發之大圖片內存溢出優化

摘要：縮放加載加載大圖片使用大圖片時可能出現的異常在下采用來表示顏色每個像素占圖片手機寬縮放高縮放需要考慮的問題動態獲取圖片的分辨率動態獲取手機分辨率實現步驟獲取手機屏幕的寬和高獲取圖片的寬和高創建的配置參數設置的值為此時方法并不會去真正縮放加載加載大圖片（使用大圖片時可能出現的異常） 09-14 00:59:51.813: E/AndroidRuntime(2128): Caused b...

yibinnn 2019-08-14 17:06 評論0 收藏0
【Vue原理】Slot - 源碼版之作用域插槽

摘要：通過函數參數傳遞的形式，讓插槽的變量，在解析時，先訪問函數變量。那么這兩個有什么關系呢外殼節點保存著所有父組件里給這個子組件綁定的數據，比如，插槽等。寫文章不容易，點個贊唄兄弟專注 Vue 源碼分享，文章分為白話版和源碼版，白話版助于理解工作原理，源碼版助于了解內部詳情，讓我們一起學習吧研究基于 Vue版本【2.5.17】如果你覺得排版難看，請點擊下面鏈接或者拉到下面...

tolerious 2019-08-23 18:29 評論0 收藏0