博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
数据结构java版之大O表示法
阅读量:6377 次
发布时间:2019-06-23

本文共 963 字,大约阅读时间需要 3 分钟。

大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次

转载地址:http://duxqa.baihongyu.com/

你可能感兴趣的文章
2017必备的八款最佳反勒索软件工具
查看>>
从Effective Java总结一些有助安卓开发的建议
查看>>
以一当十的程序员不是传说
查看>>
Vizinex RFID 和Brady SmartID推出航空标签
查看>>
Facebook 否认趋势话题存在政治偏见,但将做出调整
查看>>
云纵发布“纵横客“ 新一代互联网CRM开启餐饮行业营销新模式
查看>>
物联网到底何时才能称为“爆发”?
查看>>
《Java多线程编程核心技术》——1.2节使用多线程
查看>>
不用惊慌 关于苹果警告的一些分析
查看>>
《VMware 网络技术:原理与实践》—— 2.3 OSI模型
查看>>
金融安全资讯精选 2017年第十五期:普华永道消费者隐私信息保护调研称69%的企业无力面对网络攻击,中小银行转型系统整合中的建议...
查看>>
读书笔记之《实战Java虚拟机》(9):Class 文件结构
查看>>
面对区块链这项全新的技术,传统投资产生了焦虑
查看>>
1024城市峰会 | 当A.I.邂逅古都西安
查看>>
好看的卡片阴影
查看>>
理解 Mach O 并提高程序启动速度
查看>>
Vue实战篇(PC端商城项目)
查看>>
每周记录(二)
查看>>
你要做的是产品经理,不是作图经理!
查看>>
编码、摘要和加密(一)——字节编码
查看>>