渐近分析

“An engineer will do for a dime what any fool will do for a dollar.”

Asymptotics I

让我们先考虑一个问题：给定一个排好序的数组，如何判断数组中是否存在重复的元素？

有两个思路：

• 从头开始遍历数组，每两个元素之间都比较是否相等：

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

• 也是从头开始遍历，但只比较两个相邻元素是否相等：

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

用 Stopwatch 分别测量一下这两种方法的用时，dup1 会比 dup2 慢得多：

有趣的是，如果你将输入数组的大小扩大到原来的 2 倍，dup1 的用时将变为原来的 4 倍，而 dup2 的用时将变为原来的 2 倍。

怎么会是呢

嵌套 for 循环的分析

在分析前先让我们引入一个概念：增长阶（Order of Growth）

增长阶是用于描述算法在输入规模 $n$ 趋近于无穷大时，其时间或空间需求增长趋势的数学表示。它关注的是增长率（如线性增长、平方增长等），而非具体的运行时间或内存占用值。

在分析算法复杂度时，我们通常会进行一些简化：

1. 只考虑最坏情况；
2. 忽略低阶项；
3. 忽略系数；
4. 所有操作花费时间相同。

什么意思呢？让我们具体分析一下 dup1：

如图所示，我们假设 for 循环最内层的操作花费 1 个单位时间。最坏的情况下，循环不中断地执行到尽头：

• 当 i = 0 时，内层循环执行 N - 1 次（j 从 1 到 N-1）；
• 当 i = 1 时，内层循环执行 N - 2 次（j 从 2 到 N-1）；
• 依此类推，直到 i = N-1 时，内层循环执行 0 次。

总执行步数为：

$$C = 0 + 1 + 2 + 3 + ... + (N - 2) + (N - 1) = \frac{(N - 1) \cdot N}{2}$$

即：

$$C = \frac{1}{2} N^2 - \frac{1}{2} N$$

忽略低阶项和系数后的增长阶为：$N^2$。

而 dup2 只有一层 for 循环，同理易得增长阶为 $N$。当二者的输入规模 $N$ 同时扩大到原来的 2 倍时，dup1 变成 $4N^2$，dup2 变成 $2N$，上面的现象也很容易解释了。

渐近符号

增长阶通常用大 $O$ 符号、$\Omega$ 符号或 $\Theta$ 符号表示。

Big Theta

假设函数 $R(N)$ 的增长阶为 $f(N)$，用“Big-Theta”表示法写作：

$$R(N) \in \Theta(f(N))$$

例如：

$$\begin{align} &N^3 + 3 N^4 \in \Theta(N^4) \\ &1 / N + N^3 \in \Theta(N^3) \\ &1 / N + 5 \in \Theta(1) \\ &Ne^N + N \in \Theta(Ne^N) \\ &40 \sin(N) + 4N^2 \in \Theta(N^2) \end{align}$$

Big-Theta 表示法：

$$R(N) \in \Theta(f(N))$$

意味着存在正数 $k_1$、$k_2$ 使得：

$$k_1 \cdot f(N) \leq R(N) \leq k_2 \cdot f(N)$$

例如：

对于 $40 \sin(N) + 4N^2 \in \Theta(N^2)$ ，
$R(N) = 40 \sin(N) + 4N^2$
$f(N) = N^2$
$k_1 = 3$
$k_2 = 5$

Big O and Big Omega

当然除了“Big Theta”，还有“Big O”和“Big Omega”：

• Big O：

$$R(N) \in O(f(N))$$

意味着存在正数 $k_2$ 使得：

$$R(N) \leq k_2 \cdot f(N)$$

• Big Omega：

$$R(N) \in \Omega(f(N))$$

意味着存在正数 $k_1$ 使得：

$$k_1 \cdot f(N) \leq R(N)$$

通俗地说，Big Theta 表示的关系类似于相等, Big O 类似于小于等于，Big Omega 类似于大于等于。如：

Asymptotics II（这一节被安排在并查集之后）

我们先来总结一下增长阶在运行时带来的直观影响：

当 $f(n)$ 的增长阶为：	$N \times 2$	$N + 1$
$\Theta(1)$	不影响运行时间	不影响运行时间
$\Theta(\log n)$	运行时间 + 1	运行时间影响很小
$\Theta(n)$	运行时间 × 2	运行时间 + 1
$\Theta(n^2)$	运行时间 × 4	运行时间 + n
$\Theta(2^n)$	运行时间$^2$	运行时间 × 2

嵌套 for 循环 II

搞清楚了上面的 for 循环，再来看看下面这个：

public static void printParty(int N) {
    for (int i = 1; i <= N; i = i * 2) {
        for (int j = 0; j < i; j += 1) {
            System.out.println("hello");
            int ZUG = 1 + 1;
        }
    }
}

它与前面的 for 循环的运行时间是一样的吗？

显然不一样，因为 for 循环外部的更新逻辑不同了。看上去外部循环执行 $\log N$ 次，内部循环执行 N 次，总增长阶就是 $N \log N$。

这就是我们的最终结果吗？内部循环执行的次数实际上是 i 而不是 N，只是 i 最大能取到 N 而已，所以我们只能说是 $O(N \log N)$ 而不是 $\Theta(N \log N)$。

它的运行时间实际上是什么样子？我们来仔细分析一下：

public static void printParty(int N) {
    for (int i = 1; i <= N; i = i * 2) {
        for (int j = 0; j < i; j += 1) {
            //1 unit of work
        } } }

我们仍将最内层执行的操作视为一个工作单位，

当 N = 3 时因为 3 不是 2 的幂，所以不会影响循环次数。

以此类推，最终我们会得到这样一个表示 C(N) 与 N 关系的表格：

图像大概是这样：

我们可以发现 C(N) 的图像大致在 0.5N 与 2N 之间：

所以我们可以大致估计该 for 循环的运行时间大致为 $\Theta(N)$。

为了验证我们的结论，我们再准确地计算一下：

$$1 + 2 + 4 + ... + 2^k = 2(2^k) - 1$$

当 $N = 2^k$ 时：

$$1 + 2 + 4 + ... + N = 2N - 1$$

$$\therefore R(N) \in \Theta(N)$$

渐近分析没有捷径

就像上面的例子，如果我们像一开始那样想当然地分析，得到的结果不会是准确的。准确的运行时间需要直接的数学分析。

而事实上找到每个单一函数的运行时间是不可能的，我们只能尝试去估计。不过像常用的勾股数一样，我们可以记住一些特殊的情况：

$$\begin{align} &1 + 2 + 3 + ... + Q = Q(Q + 1) / 2 = \Theta(Q^2) \\ &1^k + 2^k + 3^k + ... + Q^k = \Theta(Q^{k + 1}) \quad (k \geq 0) \\ &1 + 2 + 4 + 8 + ... + 2^Q = 2(2^Q) - 1 = \Theta(2^Q) \\ &k^0 + k^1 + k^2 + ... + k^Q = \Theta(k^Q) \quad (k > 1) \end{align}$$

这些情况之外，我们就需要通过这些策略进行分析：

• 求和
• 举例
• 画图象

摊还分析（Amortized Analysis）

摊还分析的核心思想是 平均。某些操作可能在某些时候代价较高，但通过分析整个操作序列的 平均代价，可以证明每个操作的平均时间成本较低。

例如我们之前在实现动态数组（Array List）的时候，进行 resize 操作的速度是很慢的，因为需要将旧数组中的所有元素复制到新数组中，需要消耗的运行时间为 $O(n)$。但我们改变了扩容策略后，扩容次数显著减少，与每次基本插入消耗的运行时间 $O(1)$ 均摊下来，摊还代价为 $O(1)$ / 操作。

再如并查集（Disjoint Set），虽然第一次查找根节点的时间复杂度仍然是 $O(\log n)$，但压缩路径之后的节点每次操作时间复杂度都是 $O(1)$，摊还代价为 $O(\alpha(N))$。

递归的分析

public static int f3(int n) {
    if (n <= 1)
        return 1;
    return f3(n-1) + f3(n-1);
}

对于上面这段代码，请你用直觉判断一下它的增长阶是多少？

递归看得脑子都要炸了吧？我们看一下下面这张图吧：

每次调用 f3 都会分裂出两个子节点，直到节点值为 1。总节点数为：

$$1 + 2 + 4 + ... + 2^{n - 1} = 2^n - 1$$

由于单次调用的用时是常数，则

$$R(N) = \Theta(2^n)$$

现在如果我们再做一个小改动，又会发生什么呢？

public static int fib(int n) {
    if (n <= 1)
        return 1;
    return fib(n-1) + fib(n-2);
}

虽然每次递归调用仍然会分裂出两个子节点，但现在递归树的高度不同了，因为 fib(n-2) 比 f3(n-1) 少一层递归：

所以我们可以说此时的时间复杂度是：

$$R(N) = O(2^n)$$

但如果你之前有过一定的了解，fib() 方法的作用是返回斐波那契数列中的第 n 个数，实际上的时间复杂度是：

$$R(N) \in \Theta(\varphi^N) \; \text{(其中 } \varphi = \frac{1 + \sqrt{5}}{2} \approx 1.618 \text{)}$$

二分搜索（Binary Search）

举个例子：我们如果现在想找出班里生日在 12 月 5 日的同学，我们首先将所有同学按照生日从 1 月 1 日到 12 月 31 日的顺序排序，接着取这个区间的中点，大概是 6 月 15 日与 12 月 5 日进行比较，显然 12 月 5 日要比 6 月 15 日晚，接着我们在 6 月 16 日到 12 月 31 日这个区间内重复此操作······最终我们会找到这名同学或发现这名同学不存在。

代码层面上来看大概是这样：

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;
}

你能估计出这段代码最坏情况的运行时间吗？

最坏情况是：初始总共有 $N$ 个元素，每次调用都会将元素数量减半，直到只剩一个元素。

如果 $N = 1$，调用一次后会直接返回；如果 $N = 2$，调用一次后没找到，区间中还剩一个元素所以还要再调用一次······以此类推地找下去，我们会得到这个表格：

最终我们可以得到调用次数：

$$C(N) = \lfloor \log_{2} (N) \rfloor + 1 \quad \text{(其中 } \lfloor \rfloor \text{ 表示向下取整)}$$

又每次调用花费的时间都为常数，那么总运行时间为：

$$R(N) = \Theta(\lfloor \log_{2} (N) \rfloor)$$

看起来有些复杂，但我们有一些简化的策略：

$\Theta(\lfloor f(N) \rfloor) = \Theta(f(N))$：$f(N)$ 向下取整后与 $f(N)$ 有着相同的增长阶，因为 $f(N)$ 向下取整最多取到 $f(N) - 1$，只有常数级的影响；
$\Theta(\lceil f(N) \rceil) = \Theta(f(N))$：$f(N)$ 向上取整后与 $f(N)$ 有着相同的增长阶，因为 $f(N)$ 向上取整最多取到 $f(N) + 1$，只有常数级的影响；
$\Theta(\log_{p} (N)) = \Theta(\log_{Q} (N))$：对数的底数对增长阶没有影响，因为根据换底公式，等式两边只有一个常数因子的差别。也因此，我们在分析增长阶时会将对数的底数省略。

根据以上的策略我们可以得到：

$$R(N) = \Theta(\log N)$$

归并排序（Merge Sort）

归并排序采用 分治（Divide and Conquer）策略，其核心步骤如下：

• 分解（Divide）：将数组递归地分成两半，直到子数组长度为1；
• 合并（Merge）：将两个已排序的子数组合并成一个有序数组，这是合并过程的示例：Demo

以层为单位，每一层所做的操作是分别遍历并比较两个子数组的元素，并将元素按照顺序插入本层的数组中。

层数	节点个数	每个节点大小	合并代价（单个）	总代价
1	1	$N$	$\Theta(N)$	0（根节点不会被合并）
2	2	$N/2$	$\Theta(N/2)$	$\Theta(N)$
3	4	$N/4$	$\Theta(N/4)$	$\Theta(N)$
…	…	…	…	…
$\log_2 N + 1$	N	1	$\Theta(1)$	$\Theta(N)$

根据上表，我们总共会进行 $\log_2 N$ 次合并，而每次合并的代价为 $N$，所以总运行时间为：$\Theta(N \log N)$。

现在我们再回到最开头的问题，问题给定了已经排好序的数组。如果给定的数组没有被排好序，dup1 仍然适用，但 dup2 就不行了。但如果我们在 dup2 前面先用归并排序将数组排好序，我们整个解决方案的时间复杂度便是 $\Theta(N \log N + N) = \Theta(N \log N)$，比 dup1 的 $\Theta(N^2)$ 快了不止一星半点儿：

如果我们学过了哈希，我们将能做得更好，so keep on moving！