数据结构java版之大O表示法
大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次
相关推荐
LauraRan 2020-09-28
范范 2020-07-30
mingyunxiaohai 2020-07-28
mingyunxiaohai 2020-07-19
koushr 2020-11-12
zhangxiafll 2020-11-13
kikaylee 2020-10-31
范范 2020-10-28
MILemon 2020-10-22
hugebawu 2020-10-12
shenwenjie 2020-09-24
omyrobin 2020-09-23
guangcheng 2020-09-22
qiangde 2020-09-13
hanyujianke 2020-08-18
晨曦之星 2020-08-14
xiesheng 2020-08-06
KAIrving 2020-08-02