Asymptotics

介绍

这篇文档旨在给大家介绍一些渐近分析的实用方法。我们不会讨论渐近分析的理论、必要性或者用处。本指南假设你已经了解相关知识，并且想要用它们来分析 Java 方法的运行时间。我们会介绍一些你应该掌握的策略，然后讲解一些我称之为“技巧”的方法（注意：技巧有很多，这里只会介绍一部分）。

废话不多说，咱们先来聊聊一些你肯定要掌握的数学知识。

数学背景

你只需要掌握一些和渐近分析相关的基础数学知识。主要包括两部分：简化求和的方法，以及快速计算序列元素个数的技巧。

求和

渐近分析的核心就是把问题转化为求和，然后应用正确的求和公式。在 CS 61B 课程中，你会遇到两种求和类型：算术求和和几何求和。

算术求和

算术求和指的是，相邻两项的差是一个常数的求和。这个常数具体是多少并不重要。例如：

$1 + 2 + 3 + 4 + 5 + ... + N$

$1 + 3 + 5 + 7 + 9 + 11 + ... + N$

$10 + 20 + 30 + 40 + 50 + ... + N$

都是算术求和。

对于算术求和，整个求和的结果是最后一项的平方的$\Theta$级别。所以，即使这些算式中的常数不一样，它们的结果都是$\Theta(N^2)$。 是不是简单到难以置信？但它确实就是这么简单。

看似很难的问题：以下总和的 $\Theta$ 界限是什么：

$1 + 2 + 3 + 4 + 5 + ... + \log N$

你可能觉得这个式子很难，因为里面有$\log N$。但是别忘了你刚学到的：找到最后一项，平方，然后加上$\Theta$。所以，这个求和的结果就是$\Theta(\log^2 N)$。 看，是不是很简单？现在让我们讨论下一种求和类型。

几何求和

可以说是更容易的求和。几何求和指的是，相邻两项的比值是一个常数的求和。例如：

$1 + 2 + 4 + 8 + ... + N$

$1 + 3 + 9+ 27 + ... + N$

$10 + 100 + 1\,000 + 10\,000 + ... + N$

对于几何求和，你只需要关注最后一项，仅此而已。 不需要平方。 找到最后一项，加上一个$\Theta$，就搞定了。 所以，没错，上面这些几何求和的结果都是$\Theta(N)$。

看似很难的问题：以下总和的界限是什么：

$$ 1 + 2 + 4 + 8 + 16 + ... \sqrt{\log N}$$

你可能已经掌握了诀窍。 现在你已经学会了方法，这题对你来说应该不难了！ 观察前几项可以发现，这是一个几何求和，所以我们只需要把最后一项加上$\Theta$。 因此，这个求和的结果是$\Theta(\sqrt{\log N})$。 小菜一碟！

求和总结

我们来快速总结一下求和的知识点。 遇到求和问题，按照下面两步走：

1. 观察求和式的前几项，判断它是哪种类型（算术求和还是几何求和）。
2. 找到最后一项，然后进行相应的简化（如果是算术求和，就平方，然后加上$\Theta$；如果是几何求和，直接加上$\Theta$）。

序列

序列和求和有些不一样。 序列不是对一堆东西求和，而是一系列数字的列表。以下是序列：

$1, 2, 3, 4, 5, ... , N$

$1, 2, 4, 8, 16, ... , 2^N$ 注意这里是逗号，而不是加号“+”。

这里没有“算术序列”或“几何序列”的概念，只有序列。通常，我们会将 Java 方法中所做的工作归结为一个数字序列，我们只想知道这里有多少个数字。所以，我建议你这么做。

你需要知道最后一项。我们假设它是关于 $N$ 的一个函数，记作 $g(N)$。因此，对于上面的例子，第一个序列的 $g(N) = N$，第二个序列的 $g(N) = 2^N$。

1. 找出序列中第 $i$ 项的表达式，称之为 $f(i)$。怎么写 $f(i)$ 的表达式更简洁就怎么来，你可以选择从 0 开始索引，也可以从 1 开始索引。从 0 开始索引意味着 $f(0)$ 是第一项，从 1 开始索引意味着 $f(1)$ 是第一项。
2. 创建一个名为 $k$ 的新变量，并将序列中的元素个数设置为 $k$。我们的目标是确定 $k$。
3. $g(N) = f(k)$，然后解出 $k$。如果对为什么要这么做感到困惑，请回头阅读关于 $g(N)$ 和 $f(i)$ 的定义。

就是这样。让我们对上面的两个序列进行操作。 $1, 2, 3, 4, 5, ... , N$ 其实这里没必要这么做，因为显然有 $N$ 个元素。不过，就当是热身吧。

$g(N) = N$ 且 $f(i) = i$。显而易见。注意，这里我们使用了从 1 开始的索引方式。

$g(N) = f(k)$

$N = k$

好，搞定。所以这个序列中有 $N$ 个元素。继续下一个。

$1, 2, 4, 8, 16, ... , 2^N$

这个稍微复杂一些，不过你可能在脑子里就能算出来。无论如何，让我们求出 $g(N)$ 和 $f(i)$。

$g(N) = 2^N$ 且 $f(i) = 2^i$。请注意，这里我们从 0 开始索引元素。

$g(N) = f(k)$

$2^N = 2^k$

$N = k$

就是这样！现在让我们讨论一个你会看到很多的序列，你最好把它记住，省得每次都推导。

$1, 2, 4, 8, 16, ..., N$

$g(N) = N$ 且 $f(i) = 2^i$。

$g(N) = f(k)$

$N = 2^k$

$k = \log_2(N)$

瞧。记住，对于渐近分析，$\log$ 的底数并不重要，所以我们可以简单地说 $k$ 是 $\Theta(\log N)$。

这是一个难题，我留给你自己去做：

$2, 4, 16, 256, 65536, 4294967296, ... N$

这些数字看起来可能很随机，但我建议将每个数字写成 2 的幂。你可以使用与上面相同的步骤来解决这个问题。可以问问助教、朋友，或者在 Ed 上发帖求助。

至此，我们已经复习了数学背景。你很快就会明白这些东西有多重要。如果你只是记住了到目前为止所说的内容也没关系。但从现在开始，你不应该记住任何公式。只要记住策略。废话不多说，我们直接来看单层循环的 Java 方法！

单层循环

这是渐近分析问题的核心。你很快就会明白我们上面所做的那些数学知识有多重要。首先，我们来看几个 Java 方法的例子，它们大概长这样：

public void loop1(int N) {
    for (int i = 0; i < N; i = i + 1) {
        System.out.println(i);
    }
}

这是一个非常标准的函数。我们再来看一个例子。

public void loop2(int N) {
    for (int i = 0; i < N*N; i = i + 1) {
        int[] x = new int[i];
    }
}

再看一个例子。

public void loop3(int N) {
    for (int i = 1; i < N; i = i * 2) {
        int x = i;
    }
}

我想我们看得差不多了。这些函数里面的内容大同小异。不用着急计算这些代码的运行时间，我们稍后会进行分析。

这些函数之间只有以下 3 点不同：

1. 循环的退出条件。假设 $i$ 的最大值是 $g(N)$。这意味着循环退出的条件是 $i < g(N)$。
2. $i$ 如何根据前一次迭代的值进行更新。
3. 每次循环中执行的操作量，作为 $i$ 的函数。将此函数称为 $f(i)$。

掌握了这些要素，我们就可以通过求和快速确定函数的运行时间：

$f(i_1) + f(i_2) + f(i_3) + ... + f(g(N))$

其中，$i_1$ 是 $i$ 的初始值，$i_2$ 是 $i$ 的第二个值，以此类推。$i$ 的递增方式决定了这些值的大小。$g(N)$ 代表 $i$ 的最终取值，因此 $f(g(N))$ 代表最后一次迭代所执行的操作量。

在实际问题中，你需要确定函数 $f, g$ 以及数列 $i_1, i_2, i_3, ...$，然后根据相应的公式简化求和（例如，等差数列求和需要对末项平方，等比数列则不需要）。

就是这样。让我们回到 loop1 的例子，看看如何应用这些步骤。

循环 1

public void loop1(int N) {
    for (int i = 0; i < N; i = i + 1) {
        System.out.println(i);
    }
}

1. $i < N$ 是退出条件，所以 $g(i) = N$
2. $i = i + 1$ 是递增函数
3. ???

希望大家理解了前两步的推导过程。我只是观察了 for 循环的结构，这两点信息就藏在其中。很简单，不是吗？

每次循环执行的操作量是多少呢？ 答案是 1。如果感到困惑，也没关系。为什么是 $1$？因为打印一个整数是一个常数时间操作。换句话说，System.out.println(i) 的时间复杂度是 $\Theta(1)$。它的运行时间与 $i$ 无关。可以将其理解为一个定义。

好了，现在我们进入下一步：进行求和。

$f(i_1) + f(i_2) + f(i_3) + f(i_4) + ... + f(g(N))$

我们知道 $i_1 = 0, i_2 = 1, i_3 = 2, i_4 = 3$，以此类推。此外，我们知道 $g(N) = N$。

$f(0) + f(1) + f(2) + f(3) + ... + f(N)$

我们知道 $f(i) = 1$，所以：

$1 + 1 + 1 + 1 + ... + 1$

这个求和非常简单，就是将 1 重复相加。那么，一共有多少项呢？观察 $i$ 的取值，可以发现它构成了一个简单的数列，显然数列共有 $N$ 项。因此，求和结果可以简化为 $N \cdot 1 = N$，其时间复杂度为 $\Theta(N)$。 需要注意的关键是：如果每次迭代的工作量与 $i$ 无关（是常数），你只需计算迭代的次数，然后用 $\Theta$ 表示即可。

接下来，我们来看稍微复杂一些的 loop2。

Loop 2

public void loop2(int N) {
    for (int i = 0; i < N*N; i = i + 1) {
        int[] x = new int[i];
    }
}

1. $i < N^2$ 是退出条件，所以 $g(i) = N^2$
2. $i = i + 1$ 是递增函数
3. ???

同样，前两点很容易从代码中直接得到。

那么，作为 $i$ 的函数，每次迭代完成的工作量是多少呢？ 循环体内部的操作稍微复杂。 因为它创建了一个长度为 $i$ 的数组，所以需要 $i$ 的工作量 (需要为每个索引分配内存空间)。 因此，$f(i) = i$。

好了，现在我们准备好进行下一步：写出求和表达式。

$f(i_1) + f(i_2) + f(i_3) + f(i_4) + ... + f(g(N))$

我们知道 $i_1 = 0, i_2 = 1, i_3 = 2, i_4 = 3,$ 等等。 此外，我们知道 $g(N) = N^2$。

$f(0) + f(1) + f(2) + f(3) + ... + f(N^2)$

我们知道 $f(i) = i$，所以：

$0 + 1 + 2 + 3 + ... + N^2$

这个求和表达式看起来眼熟吗？ 应该的。观察前几项，我们发现这是一个等差数列，所以取最后一项 $N^2$，平方后得到 $N^4$，因此最终结果是 $\Theta(N^4)$。 搞定！

最后，让我们做 loop3。

Loop 3

public void loop3(int N) {
    for (int i = 1; i < N; i = i * 2) {
        int x = i;
    }
}

1. $i < N$ 是退出条件，所以 $g(i) = N$
2. $i = i * 2$ 是递增函数
3. ???

同样，前两点很容易从代码中直接得到。

作为 $i$ 的函数，完成的工作量是多少？它是常数。不是 $i$ 的函数。所以，$f(i) = 1$。

现在，我们可以继续按部就班地解决这个问题，或者回想一下我之前强调的重点。我再重复一遍。

需要注意的关键是：如果每次迭代的工作量与 $i$ 无关（是常数），你只需计算迭代的次数，然后用 $\Theta$ 表示即可。

让我们列出 $i$ 的取值序列：

$i_1, i_2, i_3, i_4, ... , g(N)$

$1, 2, 4, 8, ... N$

我们已经基本完成了。 实际上，我们在上一节已经分析过类似的情况。 我们知道这个序列包含 $\Theta(\log N)$ 项。 因此，该 Java 函数的时间复杂度，也就是迭代次数，为 $\Theta(\log N)$。 搞定！

单循环 Java 方法总结

我们学习了一种处理这些问题的方法。

1. 找出 $i$ 的最后一个值，作为 $N$ 的函数。称之为 $g(N)$。
2. 找出 $i$ 的递增函数。
3. 找出每次迭代完成的工作量，作为 $i$ 的函数。称之为 $f(i)$。

有了以上这些，你就可以写出如下的求和表达式： $f(i_1) + f(i_2) + f(i_3) + f(i_4) + ... + f(g(N))$ 通过观察 $i$ 的递增方式，就能确定 $i_1, i_2, i_3, i_4, ...$ 的值。然后，将已知的值代入，化简求和式。 好了，就这样。

我们还发现，如果 $f(i) = 1$ (也就是说，for循环内的操作与 $i$ 无关，是常数级别的)，那么可以直接计算出序列 $i_1, i_2, i_3, i_4, ...$ 中元素的个数，然后用 $\Theta$ 表示。

练习一些类似的题目后，你也许就能一眼看出单循环的时间复杂度了。 这很棒!

你也许觉得我把问题讲复杂了。 确实有一些捷径。 你说的没错，捷径是有的。 但捷径太多了，我不可能在这份指南里详细介绍每一种。这对初学渐近分析的人来说，帮助不大。 本指南的目标是提供给你解决问题的策略， 让你自己找到答案。 下一节讲双重循环的时候，你会发现这个方法非常有效，而且很容易推广。

你可能会遇到一些你无法化简的求和式，这时你可以向助教、朋友或者在Ed上发帖求助，或者干脆跳过。 例如，你可能会得到一个像这样的求和： $\sqrt{1} + \sqrt{2} + \sqrt{3} + ... \sqrt{N}$

你可以直接忽略它。 我不知道如何简化它，而且它超出了本课程的范围。

双循环

我把这一部分单独列出来，但实际上它和单循环没有什么不同。 它稍微复杂一些，所以我想和你一起讨论一下。 首先，让我向你展示一些双循环的例子：

public void dLoop1(int N) {
    for (int i = 1; i < N; i = i * 2) {
        for (int j = 0; j < 10; j = j + 1) {
            System.out.println(i + j);
        }
    }
}

非常标准。 让我们看看另一个。

public void dLoop2(int N) {
    for (int i = 1; i < N; i = i + 1) {
        for (int j = 1; j < i; j = j * 2) {
            int[] x = new int[j];
        }
    }
}

再来一个：

public void dLoop3(int N) {
    for (int i = 1; i < N * N; i = i + 1) {
        for (int j = 1; j < Math.sqrt(i); j = j + 1) {
            int[] x = new int[j];
        }
    }
}

首先，不要落入最古老的陷阱。 不要将外循环的迭代次数乘以内循环的迭代次数。 这几乎不是你应该做的。 这是一个常见的错误，许多学生会犯，因为他们试图走捷径。 捷径很好，但在你确定如何使用它们之前，不要使用它们！！

好了，言归正传，我们来说说双重循环怎么处理。 其实方法和单循环是一样的：

1. 求出 $i$ 作为 $N$ 的函数的最后一个值。称之为 $g(N)$。
2. 求出 $i$ 的递增方式。
3. 求出每次迭代完成的工作量，作为 $i$ 的函数。称之为 $f(i)$。

有了以上这些，就可以写出求和式： $f(i_1) + f(i_2) + f(i_3) + f(i_4) + ... + f(g(N))$ 你可以通过查看 $i$ 的递增方式来求出 $i_1, i_2, i_3, i_4, ...$。然后， 代入你所知道的一切，然后简化求和式。就是这样！

这里，$f(i)$ 表示内循环的工作量，它是 $i$ 的函数！

接下来，我们制定以下步骤：

1. 求出内循环的工作量，作为 $i$ 的函数。称之为 $f(i)$。
2. 利用 $f(i)$，求出外循环的工作量，并用 $\Theta$ 表示其复杂度。

注意，$i$ 在内循环中是确定的。因此，$N$ 与 $i$ 的关系，类似于 $i$ 与 $j$ 的关系。希望你能理解。也就是说，计算外循环的渐近运行时，我们关注的是 $N$ 的变化，$i$ 是循环变量；而计算内循环的工作量时，我们关注的是 $i$ 的变化，$j$ 是循环变量。

就是这样。我们以 dLoop1 为例进行说明。

双重循环 1

public void dLoop1(int N) {
    for (int i = 1; i < N; i = i * 2) {
        for (int j = 0; j < 10; j = j + 1) {
            System.out.println(i + j);
        }
    }
}

首先，求出内循环的工作量，用 $i$ 表示。一个小技巧是，只关注内循环的代码：

for (int j = 0; j < 10; j = j + 1) {
    System.out.println(i + j);
}

你注意到内循环的特点了吗？虽然用到了 $i$，但只是用来打印。因此，内循环的工作量与 $i$ 无关，是常数，即 $f(i) = 1$。

由此可见，该循环与 loop3 类似，最终复杂度为 $\Theta(\log N)$。接下来，我们分析下一个例子。

双重循环 2

public void dLoop2(int N) {
    for (int i = 1; i < N; i = i + 1) {
        for (int j = 1; j < i; j = j * 2) {
            int[] x = new int[j];
        }
    }
}

这个例子稍微复杂一些，内循环的结束条件与 $i$ 相关。

记住，我们只关注内循环的代码。

for (int j = 1; j < i; j = j * 2) {
    int[] x = new int[j];
}

我们需要求出内循环的工作量，用 $i$ 表示。注意，这里不是求内循环的渐近复杂度，而是具体的计算量（不使用 $\Theta$ 符号）。

可以得到如下求和式：

$0 + 1 + 2 + 4 + 8 + ... + i$

我们知道这个求和式是 $\Theta(i)$。

但正如前面所说，这里我们不需要使用 $\Theta$ 符号，而是要得到具体的计算量。

接下来，我们需要进行一些近似处理。

我们可以近似地认为工作量等于 $i$，因此可以近似地认为

$0 + 1 + 2 + 4 + 8 + ... + i$ 计算结果是$i$， 显然这不完全对。 但是，既然我们是在做渐近分析， 就可以允许一些近似。 请继续往下看。

所以 $f(i) = i$。

这个你已经见过很多次了， 结果很简单， 就是$\Theta(N^2)$。

所以 dloop2 的渐进运行时间为 $\Theta(N^2)$。

让我们回到之前那个有点奇怪的地方。 我们说， 因为$f(i) \in \Theta(i)$， 所以可以近似地认为$f(i) = i$。 严格来说， 这并不完全正确， 但在渐近分析中， 我们可以这么近似。 即使$f(i)$ 实际上是 $10i$， 最终结果也是一样的。 如果不信， 你可以自己代入验证一下。 所以这算是一个小技巧。

双重循环 3

最后一个：

public void dLoop3(int N) {
    for (int i = 1; i < N * N; i = i + 1) {
        for (int j = 1; j < Math.sqrt(i); j = j + 1) {
            int[] x = new int[j];
        }
    }
}

第一步是求出内循环的工作量， 将其表示为关于$i$的函数。

for (int j = 1; j < Math.sqrt(i); j = j + 1) {
    int[] x = new int[j];
}

编者注： 在本指南的早期版本（已更正）中， 循环更新语句是j = j * 2， 这会导致一个很难求和的式子 （事实上， 我也不知道怎么求）。

我将再次跳过这些步骤，直接进入求和，但你应该从头开始做。熟能生巧。

$$ 1 + 2 + 3 + 4 + ... + \sqrt{i}$$

我们知道\Theta(\(\sqrt{i}\)^2) = \Theta(i)， 同样， 为了方便计算， 我们近似地认为$f(i) = i$。

现在，对于外部循环，我们将使用这个函数 $f(i) = i$，我们得到求和：

$1 + 2 + 3 + 4 + ... + N^2$

这是一个算术求和，所以我们取最后一项，求平方，然后加上一个 $\Theta$。 所以， dLoop3 的渐进时间复杂度是$\Theta((N^2)^2) = \Theta(N^4)$。

我希望你明白这真的没有那么糟糕。只是坚持规则。

双重循环 Java 方法总结

我们学习了一种分析这类问题的方法。

1. 找出内部循环中完成的工作，作为 $i$ 的函数。称之为 $f(i)$。
2. 将此 $f(i)$ 与外部循环和完全相同的过程一起使用

和单循环不同， 你可能很难一眼就看出双循环的时间复杂度。没关系。每当我做双循环时，我总是写出来，因为如果你试图在脑海中做，很容易犯错误。这个过程经过了尝试和测试，所以只要练习使用它，你总是能做对这些。

你现在应该体会到我们做单循环的方式。它使双循环变得容易得多。你甚至可以做三循环、四循环和更多循环。但是……这非常烦人。我并不是说它超出了任何考试的范围，因为它基本上与双循环相同，我只是说它很烦人。

在进入下一节之前，你应该尝试一些函数。就像单循环一样，尝试创建你自己的具有不同 $f, g$ 函数和不同方式来递增 $i$ 的函数。你很可能会遇到一些你不知道如何简化的求和式， 这时你可以向助教、 朋友或者在Ed上提问， 实在不行， 也可以先跳过。

关于嵌套循环的渐进分析就讲到这里。现在， 你已经掌握了分析循环时间复杂度的方法， 甚至可以教给你的朋友们了！ 教学相长， 这是最好的学习方式。接下来是递归！