渐近分析
介绍
这是一份渐近分析的实用指南。我们不会讨论理论，也不会讨论为什么渐近分析是必要或有用的。本指南假设你已经了解这些知识，并希望将它们应用于查找实际 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$ bound 是什么：
\[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)$。
看似困难的问题 ：下面求和的 $\Theta$ 界是什么：
\[1 + 2 + 4 + 8 + 16 + ... \sqrt{\log N}\]你可能已经掌握了这个技巧。既然你已经掌握了方法，这对你来说就不难了！从前几项我们可以看出这是一个几何求和，所以我们只需对最后一项加上 $\Theta$ 界。因此，上面的求和是 $\Theta(\sqrt{\log N})$。非常简单。
求和总结
让我们快速总结求和课程。如果你看到一个求和，请执行以下 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$。
- 找出序列中第 $i$ 个元素的表达式。称之为 $f(i)$。你可以将序列设为 0 索引或 1 索引，哪种能让 $f(i)$ 的表达式更简洁就用哪种。0 索引意味着 $f(0)$ 是第一项，1 索引意味着 $f(1)$ 是第一项。
- 创建一个名为 $k$ 的新变量，并将序列中的元素数量设为 $k$。我们的目标是确定 $k$。
- $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$ and $f(i) = 2^i$. 请注意 here we’re 0-indexing the elements.
\[g(N) = f(k)\] \[2^N = 2^k\] \[N = k\]就这样！现在让我们讨论一个你会 经常 看到的序列，你最好记住它，而不是每次都计算。
\[1, 2, 4, 8, 16, ..., N\]$g(N) = N$ and $f(i) = 2^i$.
\[g(N) = f(k)\] \[N = 2^k\] \[k = \log_2(N)\]好了。记住，对于渐近分析来说，对数的底数无关紧要，所以我们可以说 $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 样东西发生了变化：
- 循环的退出条件。假设 $i$ 能取到的最大值是 $g(N)$。这意味着我们的退出条件是 $i < g(N)$。
- $i$ 每次迭代如何递增，作为前一个 $i$ 的函数。
- 循环内部完成多少工作量，作为 $i$ 的函数。称这个函数为 $f(i)$。
有了这些，我们可以通过构建一个求和式来快速找到函数的运行时间：
\[f(i_1) + f(i_2) + f(i_3) + ... + f(g(N))\]这里，$i_1$ 是 $i$ 的第一个值，$i_2$ 是第二个值，以此类推。$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);
}
}
- $i < N$ 是退出条件，所以 $g(i) = N$
- $i = i + 1$ 是递增函数
- ???
我希望你明白我们是怎么得到前两个的。我只是看了一下for循环，就是最后那两个东西。很简单对吧？
每次迭代所做的工作量是多少（作为 $i$ 的函数）？嗯，它就是 $1$。你可能感到困惑，这没关系。为什么是 $1$？因为打印一个整数是一个
常数时间
操作。另一种说法是
System.out.println(i)
是 $\Theta(1)$。它不依赖于 $i$。所以我们说 $f(i) = 1$。把这当作一个定义。
好的，现在我们准备好进行下一步：构建求和式。
\[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 \in \Theta(N)$。
重要的一点要注意：如果每次迭代所做的工作相对于 $i$ 是常数，你可以简单地 计算迭代次数 并在其上加上 $\Theta$。
让我们来做
loop2
，它稍微复杂一些。
循环 2
public void loop2(int N) {
for (int i = 0; i < N*N; i = i + 1) {
int[] x = new int[i];
}
}
- $i < N^2$ 是退出条件，所以 $g(i) = N^2$
- $i = i + 1$ 是递增函数
- ???
同样，前两个并不难得到。只需阅读代码。
每次迭代所做的工作量是多少（作为 $i$ 的函数）？内部稍微复杂一些。它创建了一个长度为 $i$ 的数组，这做了 $i$ 的工作量（因为需要为每个索引创建一个内存盒子）。因此，$f(i) = i$。
好的，现在我们准备好进行下一步：构建求和式。
\[f(i_1) + f(i_2) + f(i_3) + f(i_4) + ... + f(g(N))\]We know that $i_1 = 0, i_2 = 1, i_3 = 2, i_4 = 3, $ and so on. Also, we know that $g(N) = N^2$.
\[f(0) + f(1) + f(2) + f(3) + ... + f(N^2)\]我们知道 $f(i) = i$，所以：
\[0 + 1 + 2 + 3 + ... + N^2\]这个求和看起来眼熟吗？应该眼熟。我们看前几项确定它是算术级数，所以我们取最后一项，平方，然后加上 $\Theta$。最后一项是 $N^2$，平方后得到 $N^4$，加上界得到最终答案 $\Theta(N^4)$。完成。
最后，让我们来做
loop3
。
循环 3
public void loop3(int N) {
for (int i = 1; i < N; i = i * 2) {
int x = i;
}
}
- $i < N$ 是退出条件，所以 $g(i) = N$
- $i = i * 2$ 是递增函数
- ???
同样，前两个并不难得到。只需阅读代码。
每次迭代所做的工作量是多少（作为 $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 方法总结
我们学到了一个处理这些问题的策略。
- 找出 $i$ 的最后一个值（作为 $N$ 的函数）。记为 $g(N)$。
- 找出 $i$ 的递增函数。
- 找出每次迭代所做的工作量（作为 $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$。
做了一些这类问题后，你可能能够一眼就看出单个循环的运行时间。那很好！
你可能认为我把事情复杂化了。有捷径。是的，有捷径。但捷径太多了。我不可能在这本指南中详细说明你能采取的每一个捷径，而且对于一个正在学习渐近分析的人来说，这也没有帮助。我的目标是给你 策略 来自己找出答案。在下一节我们做双层循环时，你会看到这种方法的优势，而且非常容易扩展。
在进入下一节之前，你应该尝试几个函数。尝试用不同的 $f, g$ 函数和不同的 $i$ 递增方式创建你自己的函数。你 可能 会遇到不知道如何简化的求和，你应该问助教/朋友/在 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];
}
}
}
首先，不要落入最老套的陷阱。不要将外层循环的迭代次数乘以内层循环的迭代次数。这几乎不是你应该做的。这是许多学生犯的常见错误，因为他们试图走捷径。捷径很好，但除非你确定知道如何使用它，否则不要使用它！！
说完这个，让我们谈谈你该怎么做。这实际上与单层循环是一样的：
- 找出 $i$ 的最后一个值（作为 $N$ 的函数）。记为 $g(N)$。
- 找出 $i$ 的递增函数。
- 找出每次迭代所做的工作量（作为 $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$ 的函数！！
所以，让我们为自己制定步骤：
- 找出内层循环的工作量，作为 $i$ 的函数。称之为 $f(i)$。
- 使用这个 $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$。
现在我们做单层循环的步骤，得到这个求和式：
\[1 + 2 + 3 + 4 + ... + N\]你现在已经见过很多次了。它就是 $\Theta(N^2)$。
所以
dloop2
的渐近运行时间是 $\Theta(N^2)$。
回到之前的奇怪说法。我们说既然 $f(i) \in \Theta(i)$，那么 $f(i) = i$。这 generally 并不正确，但对于渐近分析我们可以这样说。如果 $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 方法总结
我们学到了一个处理这些问题的策略。
- 找出内层循环所做的工作量（作为 $i$ 的函数）。记为 $f(i)$。
- 用这个 $f(i)$ 和外层循环，使用完全相同的过程
与单层循环不同，你可能 无法 一眼就看出双层循环的运行时间。这没关系。每当我做双层循环时，我总是把它写出来，因为如果你试着在脑子里做很容易出错。这个过程是经过验证的，所以只要练习使用它，你总是能正确地解答这些问题。
你现在应该感激我们处理单层循环的方式。它让双层循环变得容易得多。你甚至可以做三层、四层及更多层循环。但是……那真的很烦人。我并不是说它超出了任何考试的范围，因为它基本上与双层循环相同，我只是在说它很烦人。
在进入下一节之前，你应该尝试几个函数。就像单层循环一样，尝试用不同的 $f, g$ 函数和不同的 $i$ 递增方式创建你自己的函数。你更可能遇到不知道如何简化的求和，你应该问助教/朋友/在 Ed 上发帖，或者就留它不做。
这就是嵌套循环渐近分析问题的全部内容。你现在有资格做循环问题并教你的朋友，因为这是绝对最好的学习方法。下一节是递归！