UCB CS61B sp25 学习笔记二：Lec11~Lec14 渐进分析

Lecture 11 - Asymptotics I

一、引入：给定数组A，A中元素满足单调不减，如何得知A中是否有重复元素？

思路1：对于数组中每一个元素，都遍历一次自己后面的元素，依次进行判断。

public static boolean dup1(int[] A) {
    for (int i = 0; i < A.length - 1; i ++ ) {
        for (int j = i + 1; j < A.length; j ++ ) {
            if (A[i] == A[j]) {
                return true;
            }
        }
    }
    return false;
}

思路2：由于数组单调不减，因此若存在相同元素$a_{i}$和$a_{j}$，那么$a_{i}$和$a_{j}$必定是连续的两个元素，所以对于每个元素$a_{i}$，只需要判断$a_{i} = a_{i + 1}$是否成立即可。

public static boolean dup2(int[] A) {
    for (int i = 0; i < A.length - 1; i ++ ) {
        if (A[i] == A[i + 1]) {
            return true;
        }
    }
    return false;
}

此处请不要认为思路1相比思路2是多么麻烦或者愚蠢，Josh此处讲解这一思路的目的应当是作为对比对象，并向学生传递一种思想：一个额外的条件，或许可以彻底改变算法复杂度。毕竟如果没有“单调不减”这个条件，思路2根本不会存在。

从原Lecture的画面中可以看到，思路2的运行时间是远远短于思路1的。

二、时间复杂度分析

像上一部分一样，对于同一个问题，有不同的解决方案时，我们就需要比较代码的优劣。代码的优劣分为两个维度：时间复杂度和空间复杂度，前者表现为代码运行时间随输入规模增长而变化的基本趋势，而后者则表现为算法运行过程中额外占用空间随输入规模增长的趋势。这里我们先仅考虑时间复杂度。

我们该如何衡量一段代码的时间复杂度？显而易见的方法是直接运行（Solution 1），然后看一下终端所显示的运行时间，越短越好。但是这种方法有两个问题：同一段代码在不同电脑上的运行时间会因为硬件不同而改变，另一方面，同种思路在不同编程语言的实现下，运行时间也会产生巨大差别。

由此，我们想到了第二种解决办法（Solution 2A）：统计代码中所有基本操作的总执行次数。

优点：与硬件无关，且无需运行代码即可进行统计。
缺点：这种统计事实上很耗时间，而且统计前必须选定一个特定的数组大小才能进行计算，而不同的数组大小，例如10000和100000，对应得到的总执行次数显然是不同的，通用性低。

那么，接下来的任务就是解决Solution 2A的上述缺点。

不改变上面这种统计总执行次数的思路，直接把数组大小设为N（Solution 2B），怎么样？

优点：除了Solution 2A的优点外，还能清晰明了地展示算法的运行时间是如何增长的。
缺点：此时得到的是一个关于$N$的函数$f(N)$，不同算法对应不同的函数，虽然已经能够反映增长趋势，但函数的具体形式仍然较为复杂，不方便直接比较。

Solution 2B

在算法分析中，我们通常更关注算法在最坏情况下的表现，因为它能够给出性能的上界；有时也会分析最好情况和平均情况。此处让我们先只研究上述代码在最好和最坏两种情况下的总执行次数，看一看思路1和思路2孰优孰劣。

两种思路在最好与最坏两种情况下的总操作次数对比

从下图我们可以得知思路2显然好于思路1，因为思路2的代码的增长阶要小于思路1。

思路1和思路2的操作总执行次数对比

三、总结

让我们考虑一个与上述问题无关的新算法，假设这个算法在最坏情况下共进行$100N^2 + 3N$次处理数组元素的操作、$2N^3 + 1$次比较操作和$5000$次打印操作，那么这个算法的运行时间大概应该是以什么样的方式增长的呢？答案是$N^3$，此处我们忽略了阶数低于3的项，因为当N充分大时，非最高次项对总执行次数增长速度的影响微乎其微；我们也忽略了最高次项的系数，因为它完全取决于具体的实现方式和运行环境，而无法反映算法在时间复杂度上的本质特征，即增长方式：线性增长、平方增长、立方增长、抑或其他增长方式。

综上所述，对于一种算法，我们取其在渐进意义下增长最快的一项，并忽略$f(N)$中的常数因子和低阶项，作为该算法的渐进时间复杂度，用$\Theta(f(N))$来表示，例如$\Theta(1)$、$\Theta(N^3)$、$\Theta(N \log N)$等。

此时$\log$的底数可以忽略，因为不同底数之间只相差一个常数倍。
所有时间复杂度为常数的算法都用$\Theta(1)$表示。

最后，需要注意的是，本节讨论的是$\Theta$表示法，它用于描述算法运行时间的渐进增长速度，后续课程还会进一步介绍$O$和$\Omega$等渐进表示法。

Lecture 12 - Ask Anything (midterm prep)

Lec12是期中考试的复习课，故略过。

Lecture 13 - Asymptotics II

前言：这节课的内容基本都是数学，笔记内容较少。

一、$\Theta$表示法

在Lec11的结尾，Josh提到了一个定义：$R(N) \in \Theta(f(N))$，当且仅当存在$k_{1}、k_{2} \in \mathbb{R}^+，N_{0} \in \mathbb{N}$，使得当$N \geq N_{0}$时，满足$k_{1} \cdot f(N) \leq R(N) \leq k_{2} \cdot f(N)$。这就是渐进时间复杂度的$\Theta$表示法。

例如：$R(N) = 4N^2 + N$，$f(N) = N^2$满足$R(N) \in \Theta(f(N))$，可令$k_{1} = 3$，$k_{2} = 5$构造证明。

二、$O$表示法和$\Omega$表示法

事实证明，$\Theta$表示法并不总是最方便的，所以我们提出了$O$表示法和$\Omega$表示法，定义如下：

$O$表示法：$R(N) \in O(f(N))$，当且仅当存在$k \in \mathbb{R}^+，N_{0} \in \mathbb{N}$，使得当$N \geq N_{0}$时，满足$R(N) \leq k \cdot f(N)$。
$\Omega$表示法：$R(N) \in \Omega(f(N))$，当且仅当存在$k \in \mathbb{R}^+，N_{0} \in \mathbb{N}$，使得当$N \geq N_{0}$时，满足$k \cdot f(N) \leq R(N)$。

其实就是分别只考虑上界和下界的表示法。

重要结论：$R(N) \in \Theta(f(N))$，当且仅当$R(N) \in O(f(N))$且$R(N) \in \Omega(f(N))$。

Lecture 14 Asymptotics III

一、计算运行时间

运行时间函数通常表现为以下两种： 1.求和：$\sum_{i = 1}^{N} f(i) = f(1) + f(2) + … + f(N)$。 2.递归：先看递归树高度，再看每一层操作的时间复杂度。

二、归并排序

归并排序是怎么得到的呢？我们需要先意识到一件事情：只有一个元素的数组显然是有序的。那么，对于有两个元素的数组，即使它当前的单调性不一定满足我们的要求，但只要把它拆成两个新的单元数组，再加以比较，就可以完成排序。

对于更多个元素的数组，应该怎样通过这种思路进行排序呢？考虑一个有四个元素的数组，应用上面的方法，我们把它拆分成两个二元数组，再分别拆成两个单元数组就可以完成比较了。这里的问题是，单元数组合并成二元数组很简单，但是两个已经有序的多元数组如何合并成一个更大的有序数组？

很简单，由于两个子数组都已经有序，因此整个区间中的最小元素一定为两个子数组的首元素之一。因此，我们只需要逐个比较数组剩余部分的首元素大小，并把符合要求的元素添加到排序后的数组末尾即可。

对于元素数量更多的数组，也是同样的排序思路，所以可以看出归并排序实际上用到了递归；从排序过程上来看，归并排序也体现了分治的思想。

图解归并排序

总结一下，归并排序的代码思路就是：

将数组不断拆分成两个规模尽可能相等的子数组，直到拆分后的每个子组的元素个数是1为止；
将相邻的两个子组合并成一个有序的大组；
不断重复步骤2，直到最终只有一个组为止。

下面是归并排序的代码实现：

public class Merge {

    private static Comparable[] originArray;
    private static Comparable[] ansArray;

    public static void sort(Comparable[] a) {
        originArray = a;
        ansArray = new Comparable[a.length];
        mySort(0, a.length - 1);
    }

    public static void mySort(int low, int high) {
        if (low >= high) {
            return;
        }

        int mid = (low + high) / 2;		//(low + high)在极端情况下可能溢出，教学代码忽略此问题，myMerge中同理。

        mySort(low, mid);
        mySort(mid + 1, high);

        myMerge(low, high);
    }

    public static void myMerge(int low, int high) {

        int mid = (low + high) / 2;

        int i = low;
        int j = mid + 1;
        int total = low;

        while (i <= mid && j <= high) {

            if (originArray[i].compareTo(originArray[j]) <= 0) {
                ansArray[total++] = originArray[i++];
            } else {
                ansArray[total++] = originArray[j++];
            }

        }

        while (i <= mid) {
            ansArray[total++] = originArray[i++];
        }

        while (j <= high) {
            ansArray[total++] = originArray[j++];
        }

        System.arraycopy(ansArray,
                 low,
                 originArray,
                 low,
                 high-low+1);
    }
}

显然，就时间复杂度而言，归并排序是$\Theta(N \log N)$的，因为拆分数组的递归树高度为$\log N$，而每一层归并操作处理的元素总数都是$N$，因此总代价为$N \log N$，无论是最好、最坏，还是平均情况下均是如此。

三、总结

这节课的前半部分仍旧是对时间复杂度渐进分析的讲解，而在后半部分，我们接触到了CS61B的第一个正式算法——归并排序。课上的内容，前面的部分已经写得很清楚了。此处我想补充的是：

归并排序是一种稳定的排序算法，即：当原数组包含若干个相等元素时，排序后的数组中这些元素的相对位置关系保持不变。
使用归并排序的情况往往有这样一种显著特征：我们可以根据某一性质将当前排序对象分为两个组，这么说可能有些抽象，感兴趣的读者可以看看这道题：P1309 [NOIP 2011 普及组] 瑞士轮，即是这句话的最佳体现。

个人感想及总结

这篇学习笔记的产出历程相当艰辛，在Lecture 14完稿的前一天，我的电脑因模具和显示器的问题被送去修理，差不多一周后才返回我的手中。不过没关系，好在我终于是在到手当天就写完了这篇博客。

回到Lecture 11~14，这一部分对算法学习的历程是至关重要的，因为时空复杂度分析之于算法和数据结构就好比线性代数之于人工智能，有着命根子一般的地位。CS61B毕竟不是一门速成课，不可能一上来就从各种算法和数据结构讲起，相反，Josh要的是打牢基础，然后再慢慢深入，这样才能真正学精学透。

那么，就让我们向着后面的Lecture继续前进吧。

CS61B 技术