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

wudengzan 发布于2019-08-16 15:09 / 2936人阅读

摘要：二分查找法要查找的数数组长度设定的数组花了多少次找到最小值最大值当前猜的值打印猜的每个数找到了花了次如果猜的数大于选定的数，则把设为猜的数，否则把设为猜的数请输入大于等于的正整数且查找的数不能大于数组里最大的数调用方法执行结果找到了花了次

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

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/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