算法性能优化之二分法与二次问题

性能优化小案例

1、二分法查找

有序数组查找

有序数组是什么?

如果一个数组中的值是按一定顺序排列的,我们就称为有序数组

例如:数组 [2, 8, 15, 24, 66, 88, 100]

现在希望完成一个函数来实现:查找某个数字是否存在数组中。例如:

24 存在数组中,索引值是 3,1000 不在数组中

线性查找

方法一:我们使用暴力查找方法,通过遍历整个数组来判定该数字是否存在

public static int orangeFind(int[] array, int aim) {
    for (int i=0; i<array.length; i++) {
        if (aim == array[i]) {
            return i;
        }
    }
    return -1;
}

方法一的时间复杂度为:O(N)

方法二:二分法查找

因为数组是有序的,因此我们可以先比对中间索引值对应的数值,再来缩小查找范围

以数字 15 为例,步骤为:

  1. 先选取索引值为 3 的数值(24),由于 15<24,则舍弃 24 右边部分的数值
  2. 在左边部分中选取索引值为 1 的数值(8),由于 15>8,则舍弃 8 左边部分的数值
  3. 最后剩下 array[2],对比发现,这个就是我们想要的

如上,只需要三步就能找到对应的元素,代码如下:

public static int orangeFind(int[] array, int aim) {
    // 初始化left = 最左侧, right = 最右侧
    int left = 0;
    int right = array.length - 1;
    
    // 当left > right则表示遍历完成
    while (left <= right) {
        // 获取中间的值
        int middle = (left + right) / 2;
        int middleValue = array[middle];
        if (middleValue == aim) {
            // 已经找到目标
            return middle;
        } else if (maddleValue < aim) {
            // 目标在middle的右侧,重置left
            left = middle + 1;
        } else {
            // 目标在middle的左侧,重置right
            right = middle - 1;
        }
    }
    return -1;
}

接下来我们例举一些数据量比较大的例子,对比一下各自查找的时间复杂度:

我们只考虑最坏的情况,因为最好的情况都是 1 次,没有比较的价值

暴力查找 二分法查找
时间复杂度 O(N) O(log(N))
数组 100 个 100 6.64
数组 1w 个 1w 13.28
数组 100w 个 100w 19.93

由表中数据可知,数组越大,数据量越大,最终性能提升相当的明显,相差的不止一个档次

2、二次问题

题目:假设给定一个数字数组,数组里面每个数字都介于 0~10 之间,请找出里面重复的数字

举个例子:

数字数组为:[0, 8, 6, 2, 5, 6, 8, 6, 10, 8]

重复数字为:[8, 6]

方法一:暴力破解法

每次获取一个元素,依次判断这个元素和之后的元素是否有重复

第一步,我们选择第一个元素0,判断与后面8个元素是否相同

第二步,我们选择第二个元素8,判断与后面7个元素是否相同

代码如下:

public static ArrayList<Integer> repeat(int[] array) {
    ArrayList<Integer> result = new ArrayList<>();
    for (int i=0; i<array.length; i++) {
        // 判断第i个位置的元素和后面第j个位置的元素是否相等
        for (int j=i+1; j<array.length; j++) {
            if (array[i] == array[j]) {
                // 判断result数组是否含有该元素,如果没有,则添加该元素
                if (!result.contains(array[i])) {
                    result.add(array[i]);
                }
            }
        }
    }
    return result;
}

方法一的时间复杂度是多少呢?有两个for循环嵌套,所以是:O(N^2)(此处不包括contains方法的复杂度)

方法二:标记法

由于题干中说每个数字都是介于 0 ~ 10 之间的,那么我们猜想,可以使用 长度为11的数组来标记 0 ~ 10 这 11 个数字是否存在,1表示存在一次,2表示存在两次,n就表示存在n次

假设有一个数组为 8, 6, 5,那么我们建立长度为11的数组中,索引为8, 6, 5的位置会被标记成 1

如何判断是否重复?

下次如果遇到对应的位置的值 >= 1,则表示重复了。我们最终也只需要得到对应值 > 1 的索引的值就知道哪几个元素是重复的

详细步骤:

  1. 前置步骤:我们首先 new 一个数组,数组名称为 exist,表示该数字是否存在。数组的长度为 11,并且数组里面的值都默认为 0,表示 0 ~ 10 这 11 个数都默认不存在

  2. 第一步,我们扫描到数字 0,因此我们将 exist 数组中索引值为 0 的数字设置为 1

    exist[0] = 1;
    
  3. 第二步,我们扫描到数字 8,因此我们将 exist 数组中索引值为 8 的数字设置为 1

    exist[8] = 1;
    
  4. …依此类推

  5. 第六步的时候,我们的 exist 数组0,8,6,2,5 索引位置已经设置为 1。我们扫描到原始数组第 6 位为 6,而 exist 数组中索引值为 6 的位置的值已经为 1 了,所以我们知道 6 重复了,然后将 6 写进 result 数组中,并且将 6 对应的索引值改为 2,表示出现过 2 次了

  6. 之后再遇到 6 怎么办

    这时候不能继续往 result 中添加元素了,需要判断对应标记为 1 时,才添加到 result

完善代码:

public static ArrayList<Integer> repeat(int[] array) {
    ArrayList<Integer> result = new ArrayList<>();
    int[] exist = new int[11];
    for (int i=0; i<array.length; i++) {
        int value = array[i];
        // 判断当前exist数组是否存在该value值,如果当前已经存在该value,那么标识重复,添加到result数组中, >1的情况则不添加到result数组中,防止result中重复出现value值
        if (exist[value] == 1) {
            result.add(value);
        }
        // 将数值记录到exist数组对应索引中
        exist[value]++;
    }
    return result;
}

很明显,从代码可以看出,一次循环就能完成题目要求,所以时间复杂度为 o(N)。有人可能有疑惑,多声明了exist一段空间,空间复杂度不就提高了吗?

这其实是空间换时间的经典案例。在编程中除非特殊情况,我们只考虑时间复杂度,忽略空间复杂度

两个方法的效率差距:

方法一 方法二
时间复杂度 O(N^2) O(N)
数组 100 个 1w 100
数组 1w 个 1亿 1w
数组 100w 个 1w亿 100w

从中我们可以发现:随着数组数量的增加,性能差距也会越来越明显

上一篇:【无标题】


下一篇:招标服务费计算小程序(2022-2-10)重写