數(shù)據(jù)結(jié)構(gòu)java版之大O表示法

wudengzan 發(fā)布于2019-08-16 15:09 / 2968人閱讀

摘要：二分查找法要查找的數(shù)數(shù)組長(zhǎng)度設(shè)定的數(shù)組花了多少次找到最小值最大值當(dāng)前猜的值打印猜的每個(gè)數(shù)找到了花了次如果猜的數(shù)大于選定的數(shù)，則把設(shè)為猜的數(shù)，否則把設(shè)為猜的數(shù)請(qǐng)輸入大于等于的正整數(shù)且查找的數(shù)不能大于數(shù)組里最大的數(shù)調(diào)用方法執(zhí)行結(jié)果找到了花了次

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

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

/**
* 二分查找法
* @param search 要查找的數(shù)
* @param total 數(shù)組長(zhǎng)度
*/
public void compute(int search,int total){
//設(shè)定的數(shù)組
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;
//當(dāng)前猜的值
int current;
while (true){
sum ++ ;
current = (min + max) / 2;
//打印猜的每個(gè)數(shù)
System.out.println(current);
if(num[current] == search){
System.out.println("找到了,花了" + sum + "次");
return;
}else{
//如果猜的數(shù)大于選定的數(shù)，則把max設(shè)為猜的數(shù)，否則把min設(shè)為猜的數(shù)
if(num[current] > search){
max = num[current] ;
}else{
min = num[current];
}
}

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

調(diào)用方法：

compute(3,100)
執(zhí)行結(jié)果：

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