衡量算法的好坏和二分查找改动版
我们在学习二分查找法基础版时会有疑惑
明明二分查找难以理解,我们为什么不选择暴力遍历呢
其实暴力遍历在算法里面叫做线性查找
让我们看看二次查找和线性查找的执行次数
可以采用以下两种方式
事后统计法
通过代码跑一遍 需要大量数据测并且对硬件有要求 不推荐
事前分析法
1.分析最差的执行情况
2.假设每行语句执行的时间是一样的
不然无法分析
即最差的情况就是执行到最后一行代码 for循环次数拉满
下面是线性查找
下面是二分查找
放一起
我们将这两种方法引入图片中
我们发现当数据很大时,二分查找所用的次数远远低于线性查找
时间复杂度
是用来衡量随着一个算法的执行,随着数据规模的增大,而增长的时间的成本
注:不依赖于环境因素 硬件cpu主频和内存读取速度与软件编译器
大O表示法
如图
渐进上界表示代码执行最差的情况
渐进下界表示代码执行最好的情况
大O表示法表示
用基本函数函数大于然后去掉系数
我们可以通过函数绘图工具找出表达式
如
线性查找
二分查找
总结
常见的大O表示法
O(1) 常量时间 说明算法时间不会随着数据规模而变化
O(log(n))对数时间
O(n)算法时间与数据规模成正比
O(n*log(n))拟线性时间
O(n平方)平方时间
O(2的n次方)指数时间
O(n!)阶乘时间 时间复杂度最高
三种时间复杂度表示方法
空间复杂度
与时间复杂度类似,一般也使用大O表示法来衡量,一个算法的执行随数据规模增大,而增长的额外空间成本
算法执行需要额外占据的字节数
看到这里你是不是头晕了,头晕了是正常的,因为这些东西都是概念,我的标题还有一部分注意到了吗
给大家看一个二分查找的改动版,我们又叫他平衡版本
//导入Scanner包下的类
public class Main {
public static void main(String[] args) {
//创建Scanner类的对象
Scanner sc=new Scanner(System.in);
//定义数组的长度
int n= sc.nextInt();
//输入数组的数值
int arr[]=new int[n];
for (int i = 0; i < n; i++)
arr[i]= sc.nextInt();
//输入待查找数值
int taget= sc.nextInt();
//调用二分查找法
binarySearch(arr,taget);
}
//访问修饰符public表示公有化方法 是权限最大的访问修饰符权限修饰符
//即可以可以在同一个类,同一个类的其他方法,不同包下的子类,不同包下的其他类中使用
//被static修饰的方法独立于该类的任何对象
//也就是说,这些变量和方法不属于任何一个实例对象,而是被类的实例对象所共享;
//其实意思就是都可以用
public static int binarySearch(int a[], int target){
//指定两个指针
int i=0,j=a.length;
while(1<j-i){
int m=(i+j)>>>1;
if(target<a[m])
//右指针左移
j=m;
else
//左指针右移
i=m;
}
if(a[i]==target)
//找到了
return i;
//没找到
else return -1;
};
}
我们分析一下他与二分查找基础版本的区别
如果元素在最左边要执行L次
那么元素在最右边要执行2L次
左边找元素成本低 因为只要比较一次就行
else if是造成不平衡的原因
左闭右开的区间,i指向的可能是目标,而j指向的不是目标
不在循环内找出,等范围内只剩i时,退出循环,在循环外比较a[i]和target
循环内的平均比较次数减少了
时间复杂度O-(log(n))
因为渐近上界和渐近下界一样
所以我们用渐进紧界表示(就是O中间一横 上面有)
也算是一个缺点,可以忽略,从严格意义上不算是缺点