Java基础数据结构 1.3 何如衡量算法的好坏

1.3 何如衡量算法的好坏

如：二分查找 vs 线性查找

• 事后测试法：

  • 直接拿一个数据去跑一遍，那肯定是数据量大才能体现差异。但是数据量太大，对硬件也有要求了
  • 依赖数据和硬件

• 事前分析法

  • 前提

    ​ 1. 只分析最差的执行情况

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

/**
 * <p>
 * 线性查找
 * </p>
 *
 * @author <a href= "https://github.com/zemise">Zemise</a>
 * @since 2023/6/10
 */
public class LinearSearch {
    /**
     * <p>
     * 线性查找
     * <p>
     *
     * @param a      待查找的升序数组(可以不是有序数组)
     * @param target 待查找的目标值
     * @return int   找到则返回索引，找不到就返回-1
     * @author Zemise
     * @since 2023/06/10
     */
    public static int linearSearch(int[] a, int target) {
        for (int i = 0; i < a.length; i++) {
            if (a[i] == target) {
                return i;
            }
        }

        return -1;
    }

    /*
        1.  只分析最差的执行情况
        2. 假设每一行语句执行时间一样

        对于线性查找而言：
        假设数组元素个数 n
        int i = 0;          1
        i < a.length;       n + 1次
        i ++                n次
        a[i] == target      n
        return -1;          1次

        也就是代码执行次数大概是：3*n + 3次

        对于二分法查找而言
        最差的情况是：右侧没有找到
        右侧更差的原因是取平均的时候是向下取整的，在右侧没有找到执行的次数会更多
        1 [2, 3, 4, 5] 5

        int i = 0, j = a.length -1;     2次
        return -1;                      1次
        元素个数    循环次数
        4-7          3      floor(log_2(4)) = 2 再 +1
        8-15         4      floor(log_2(8)) = 3 再 +1
        16-31        5      floor(log_2(16)) = 4 再 +1
        32-63        6      floor(log_2(32)) = 5 再 +1
        ...          ...

        循环次数L =  floor(log_2(n)) 再 +1

        i <= j;                         L + 1次
        i + j >>> 1;                    L次
        target < a[m]                   L次
        a[m] < target                   L次
        i = m + 1                       L次

        也就是代码执行次数大概是：(floor(log_2(n)) + 1) *5 + 4次

        最后代入一定的n值进行比较，会发现当 n < 4的时候，线性查找会快点
        但是，当n 数值越大的时候，二分法所用的次数远远小于线性查找

        虽然但是：
        内心OS是，这里的前提是有序数组的比较，如果遇到无序的，二分法还得排下序
        所以应该不只是4以下，线性查找比二分法快
     */
}

以上分析得出两种公式，分别对应两种算法的大概耗时，这里可以用网站作图来显示具体的差异

• 3*n + 3
• (floor(log2(n)) + 1) * 5 + 4

时间复杂度

计算机科学中，时间复杂度是用来衡量：一个算法的执行，随数据规模增大，而增长的时间成本

• 不依赖于环境因素

如何表示时间复杂度呢？

• 假设算法要处理的数据规模是n，代码总的执行行数用函数 f(n） 来表示，例如：
  • 线性查找算法的函数f(n)= 3* n+3
  • 二分查找算法的函数f(n)=(floor (log2(n)) + 1)* 5 + 4
• 为了对f(n)进行化简，应当抓住主要矛盾，找到一个变化趋势与之相近的表示法

1. 大O表示法

其中

• c，c1，c2 都为一个常数
• f(n) 是实际执行代码行数与n的函数
• g(n) 是经过化简，变化趋势与 f(n）一致的n的函数

asymptotic upper bound 渐进上界：从某个常数 n0开始， c* g(n) 总是位于 f(n) 上方，那么记作$O(g(n))$

• 举例：f(n) = n^2^+ 100，从 n0 = 10 时，g(n) = 2 * n^2^ 是它渐进上界，记作 $O(n^2)$

• 表示最糟糕的情况，再差也不会超过渐进上界了

  • 例1：
    • f(n) = 3 * n + 3
    • g(n) = n 找到她最高次项
    • 取c = 4，在n0= 3之后，g(n) 可以作为 f(n) 的浙进上界，因此表 示法写作 O(n)
  • 例2：
    • f(n) = (floor (log2(n)) + 1) * 5 + 4
    • 转为 f(n) = 5 * floor (log2(n)) + 9
    • g(n) = log2(n) 此时在来曲线的下面，再乘上一定系数就可以了
    • $O(log_2(n))$
  

asymptotic lower bound 渐进下界：从某个常数 n0开始，c* g(n) 总是位于 f(n) 下方，那么记作 $Ω(g(n))$

asymptotic tight bounds 渐进紧界：从某个常数n0开始，f(n) 总是在c1*g(n) 和c2 * g(m) 之间，那么记作$ Ɵ(g(n))$

2. 常见大O表示法

按时间复杂度从低到高

• 黑色横线$O(1)$，常量时间，意味着算法时间并不随数据规模而变化

  • 非常优秀

• 绿色$O(log_2(n))$，对数时间

  • 比较优秀

• 蓝色$O(n)$，线性时间，算法时间与数据规模成正比

• 橙色 $O(n* log(n))$，拟线性时间

• 红色$ O(n^2)$，平方时间

• 黑色朝上$ O(2^n)$，指数时间

• 没画出来的$ O(n!)$

空间复杂度

与时间复杂度类似，一般也使用大$O$表示法来衡量：一个算法执行随数据规模增大，而增长的额外空间成本

 public static int binarySearchBasic(int[] a, int target) {
        int i = 0;
        int j = a.length - 1;           // 设置指针和初始值
        while (i <= j) {                // i～j 范围内还有东西

            int m = (i + j) >>> 1;

            if (target < a[m]) {        // 目标在左边
                j = m - 1;
            } else if (a[m] < target) { // 目标在右边
                i = m + 1;
            } else {                    // 找到了
                return m;
            }
        }

        return -1;
    }

上述的空间复杂度为$O(1)$，主要是变量固定了，没有增长

p s：常量型都用$O(1)$表示

二分查找性能 下面分析二分查找算法的性能 时间复杂度

• 最坏情况：$O(log n)$
• 最好情况：如果待查找元素恰好在数组中央，只需要循环一次$O(1)$

空间复杂度

• 需要常数个指针 i, j ,m，因此额外占用的空间是 $O(1)$