数据结构java版之大O表示法

发布时间:2019-11-19 发布网站:脚本宝典
脚本宝典收集整理的这篇文章主要介绍了数据结构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 &amp;& 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次

脚本宝典总结

以上是脚本宝典为你收集整理的数据结构java版之大O表示法全部内容,希望文章能够帮你解决数据结构java版之大O表示法所遇到的问题。

如果觉得脚本宝典网站内容还不错,欢迎将脚本宝典推荐好友。

本图文内容来源于网友网络收集整理提供,作为学习参考使用,版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ:384754419,请注明来意。