CS61B Notes：15. Asymptotics II

For Loop

不是所有 for 循环的时间复杂度都是 $N^2$

参考课堂视频，有三种方法：算精确和，手动列例子和画图

两个数学结论：

从 1 开始的自然数之和： $1 + 2 + 3 + 4 + \cdots + Q = \Theta(Q^2)$
2 的各次幂之和： 1 + 2 + 4 + 8 +⋯+Q = Θ(Q)

Binary Search 二分查找法

简介：
有一个按照大小顺序排列的数组，欲确定某个数值在不在其中，即可采用二分查找法。

二分查找法将数组一分为二，并检查左右两侧和目标数值的大小，进而在某一边继续二分，直到不可分。

实现：

static int binarySearch(String[] sorted, String x, int lo, int hi) {
    if (lo > hi) return -1;
    int m = (lo + hi) / 2;
    int cmp = x.compareTo(sorted[m]);
    if (cmp < 0) return binarySearch(sorted, x, lo, m - 1);
    else if (cmp > 0) return binarySearch(sorted, x, m + 1, hi);
    else return m;
}

sorted 代表已排序的数组
x 是要查找的目标
lo 和 hi 分别代表“查找边界”（例如一个长度为 7 的经过排序的数组，初始应该是 lo 为 0，hi 为 6）
如果某个数组的长度是偶数时，这意味着他们没有明确的中点，这时遵循向下取整，也就是 int m = (lo + hi) / 2。

时间复杂度：
二分查找法的 $C(N)$ 是 $log_{2}N$ ，对于对数的时间复杂度，底数不重要，他们在 Big-O 意义上是等价的，因此简化后，时间复杂度为 Θ(logN)

Arbitrary Units of Time

我们可以通过我们的任意单位（AU）来获得对时间的总体感知

例如：
某算法的时间复杂度为 $O(n^2)$ ，当 N = 6 时，它将花费 36 个 AU 的时间

归并排序与优化

1. 选择排序：

选择排序基于两个基本步骤：

在未排序的项中找到最小的项，将其移到前面，并将其“固定”在原位。
使用选择排序对剩余的未排序/未固定的项进行排序。

选择排序的时间复杂度为 Θ(N^2)

2. 归并排序

假设有两个已排序的数组，我们要将他们按照从小到大的顺序合并为一个新的数组。它的基本步骤是：

从两个数组各自的开头开始比较，将小的那个移出添加到新的数组中
然后对新的剩下的开头数据再次比较，最终形成一个新的数组

这样合并两个已排序数组的时间复杂度是 Θ(N)

3. 优化

问题：
当面对一个很大的 N 的时候，选择排序的 AU 非常大

解决：

假设有一个 N=64 的数组，我们要对其进行选择排序。
将其拆分为两个 N=32 的数组，先对将两个 N=32 的数组分别进行选择排序
再将两个排序后的数组进行归并。

这样的 AU 会小很多，按照上图的例子分别是 4096 和 2112

4. 进一步改进：

由于归并排序的时间复杂度比选择排序小的多，所以我们可以一直将 N=64 的数组拆分，直到 N=1，这时也就不再需要选择排序了，全程进行归并排序

这时的时间复杂度 k 是 Θ(NlogN)，AU 会小得多

总结

分析算法性能需要认真思考，没有“万能捷径”
不同算法即使解决同一个问题，运行时间也可能差很多
- $N^2$ 和 $N\ logN$ 的差距很大
- $N\ logN$ 比 $N$ 慢，但比 $N^2$ 快很多

（“快”指运行的速度更快）