衡量算法的好坏和二分查找改动版

我们在学习二分查找法基础版时会有疑惑

明明二分查找难以理解,我们为什么不选择暴力遍历呢

其实暴力遍历在算法里面叫做线性查找

让我们看看二次查找和线性查找的执行次数

可以采用以下两种方式

事后统计法

通过代码跑一遍 需要大量数据测并且对硬件有要求 不推荐

事前分析法

1.分析最差的执行情况

2.假设每行语句执行的时间是一样的

不然无法分析

即最差的情况就是执行到最后一行代码 for循环次数拉满

下面是线性查找

alt

下面是二分查找

alt

放一起

alt

我们将这两种方法引入图片中

alt

我们发现当数据很大时,二分查找所用的次数远远低于线性查找

时间复杂度

是用来衡量随着一个算法的执行,随着数据规模的增大,而增长的时间的成本

注:不依赖于环境因素 硬件cpu主频和内存读取速度与软件编译器

alt

大O表示法

alt

如图

渐进上界表示代码执行最差的情况

渐进下界表示代码执行最好的情况

大O表示法表示

用基本函数函数大于然后去掉系数

我们可以通过函数绘图工具找出表达式

线性查找

alt

二分查找 alt

总结

alt

常见的大O表示法

O(1) 常量时间 说明算法时间不会随着数据规模而变化

O(log(n))对数时间

O(n)算法时间与数据规模成正比

O(n*log(n))拟线性时间

O(n平方)平方时间

O(2的n次方)指数时间

O(n!)阶乘时间 时间复杂度最高

三种时间复杂度表示方法

alt

空间复杂度

与时间复杂度类似,一般也使用大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中间一横 上面有)

也算是一个缺点,可以忽略,从严格意义上不算是缺点

全部评论

相关推荐

点赞 评论 收藏
分享
12-02 14:27
Java
点赞 评论 收藏
分享
评论
6
收藏
分享
牛客网
牛客企业服务