Chapter 2: 算法基础

操作次数

假设你有一个排序算法等待测试。你发现在一个高配电脑上算法跑了1秒，在一个2000年生产的老电脑上花了10秒。这种情况下你如何判断你的算法是快还是慢？是算法更高效，还是电脑运行速度带来的影响更大？

我们不能简单地根据运行时间来衡量算法的好坏，因为运行算法的硬件会发生变化。相反的，我们使用一个全新的概念：**操作次数 (Operations)**来衡量算法的效率。

如果你的代码在循环中执行了这样一行：a = b + c，并且该行循环了$N$次，那么我们就记为我们消耗了$N$次操作次数。

我们关注的不是这样单个操作消耗的时间多长：1ms还是10ms都不重要。相反，我们更加关注当$N$变大，操作次数的增长趋势。这就是我们所说的渐进增长 (Asymptotic Growth) 概念。我们不关心$n$与$n + 5$的差异，反而我们关注例如$n$ （线性）与$n^2$ （二次）的差异。

复杂度

这些概念用来衡量算法需要调用操作次数的渐进增长速度。

Big-O ($O$)

Big-O代表上限，或者换句话说，用来表示：

算法在最坏情况下也不会比Big-O规定的速率慢

用数学符号来表示：

$$f(n) \le c \cdot g(n)$$

例如我们的算法需要使用$n^2$的步数来解决问题，在这种情况下使用Big-O来表示就是$O(n^2)$。

虽然理论来讲将这个算法的时间复杂度归类为$O(n^3)$或者$O(2^n)$也没有问题，但我们在选取Big-O表示的时候，往往采用最紧函数约束来表示，因此在这里使用$O(n^2)$是最合适的。

Big-Omega ($\Omega$)

与Big-O相反，Big-Omega用来表示下限。也就是说在任何情况下：

我的算法至少需要运行这些数量的步数

用数学符号来表示就是：

$$f(n) \ge c \cdot g(n)$$

例如，将一个大小为$n$的数组输出出来的算法的时间复杂度是$\Omega(n)$，因为你的算法需要至少访问一次数组中每一个元素。

Big-Theta ($\Theta$)

了解了上述两个概念后，理解这个应该不会很困难了：

Big-Theta像是两者的结合体。如果用来表示时间复杂度，那么使用Big-Theta表示你的算法所用步数一定会按照这个规律进行增长。

我的算法一定会按照Big-Theta表示的那样来运行

也就是：

$$ c_1 \cdot g(n) \le f(n) \le c_2 \cdot g(n) $$

当下限和上限重合时，我们就可以使用Big-Theta。换句话说，如果$\Theta(n^2)$，那么你就一定可以得出算法一定会$O(n^2)$和$\Omega(n^2)$。

Little-o ($o$) 和 Little-omega ($\omega$)

与Big-O和Big-Omega的区别在于，Little-o和Little-omega表示 严格小于 $<$或严格大于 $>$，而前两者的关系上是允许包含边界的，也就是$\le$和$\ge$。

证明

光理解概念不行，否则考试你就傻眼了。

例Cpt2.1

按照定义，证明$T(n) = 2n^2 + 4n - 1$ 符合 $O(n^2)$

我们可能喜闻乐见地直接把“因为$n^2$是最大项，所以$O(n^2)$”直接写上去。但由于这是一个证明题，所以这样写能得到0个分数。

首先按照Big-O的定义可得：

$$f(n) \le c \cdot n^2$$

而我们的目标，就是找到常量$c > 0$，$n_0 > 0$，来让：

$$2n^2 + 4n - 1 \le c \cdot n^2 \quad \text{for all } n \ge n_0$$

下一步我们来做舍入：将左侧的所有项转化为主导项，这样就方便做比较了：

对于$n \ge 1$，$4n \le 4n^2$
$-1 \le 0$

所以我们可得：

$$2n^2 + 4n - 1 \le 2n^2 + 4n^2$$

合并右手边的式子：

$$2n^2 + 4n^2 = 6n^2$$

所以如果我们选$c=6$，不等式成立。

题解

Let $c = 6$ and $n_0 = 1$.
For all $n \ge 1$, $2n^2 + 4n - 1 \le 2n^2 + 4n^2 = 6n^2$
Therefore, $T(n) = O(n^2)$

例Cpt2.2

哪一个函数增长速度更快？$f(n) = n\log(n)$还是$g(n) = n^{1.5}$?

对于本题来讲，我们可以计算极限：$\lim_{n \to \infty} \frac{f(n)}{g(n)}$。

通过计算并对比下面的三种情况，可以得出复杂度的结论

当$\lim = 0$时，$f(n)$更小 ($f(n) \in o(g(n))$)
当$\lim = \infty$时，$f(n)$更大 ($f(n) \in \omega(g(n))$)
当$\lim = k$，$k$是常数的时候，上下都有一样的增长趋势 ($f(n) \in \Theta(g(n))$)

那么我们就可以进行一个计算了：

$$\lim_{n \to \infty} \frac{n\log(n)}{n^{1.5}} = \lim_{n \to \infty} \frac{\log(n)}{n^{0.5}}$$

套用洛必达，对上下分别求导可得：

$$\lim_{n \to \infty} \frac{\frac{1}{n}}{0.5n^{-0.5}} = \lim_{n \to \infty} \frac{1}{0.5n^{0.5}} = 0$$

由于最后的答案是$0$，我们就可以根据上方的三种情况知道，$f(n)$更小，因此$n^{1.5}$的增长速度更快。

例Cpt2.3

分析下方的代码，得出该代码的时间复杂度。

for (i = 1; i <=n; i++) {
    for (j = 1; j <= i; j++){
        sum++;
    }
}

我们不妨分析两层循环的次数。外层循环执行了$n$次，内层循环执行了$i$次，则我们一共执行了这么多个操作：

$$\text{Total} = \sum_{i=1}^{n} i$$

不难发现这是一个等差数列。你可以直接得出求和的结果为：

$$\sum_{i=1}^{n} i = \frac{n(n + 1)}{2} = \frac{n^2}{2} + \frac{n}{2}$$

这一步不需要做证明，可以直接写出来最大项。最后的结果为：

$$\Theta(n^2)$$