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

小咪咪 2022-04-23 14:28 215阅读 0赞

大O表示法使用大写字母O，可以认为其含义为"order of"（大约是）。我们可以使用大O法来描述线性查找使用了O(N)级时间，二分查找使用了O(log N)级时间，向一个无序数组中插入使用了O(1)，或常数级时间。  
下面的图总结了算法的运行时间：  
![图片描述][3972038627-5c6a7910b5ccb_articlex]

通过图我们可以比较不同的大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次

[3972038627-5c6a7910b5ccb_articlex]: /images/20220308/0e7fc5c76a904e10b4a03076413ef9b7.png