fib1 算法是错误的，因为它太慢了
fib1 的正确性没有问题，它是斐波那契定义的直接翻译；问题不在于正确性，而在于效率太低，时间复杂度是指数级的
CS170 · 第 1 讲
从印刷术到十进制，从花拉子密的算术到斐波那契数列，本章以算法的起源为起点，通过计算斐波那契数的两种算法引出指数时间与多项式时间的本质区别，并引入大 O 记号作为描述算法效率的通用语言。
本章开篇提出了一个深刻的对比：改变世界的两大思想之一是印刷术，另一个则是算法。约翰内斯·古腾堡在 1448 年发明了活字印刷，极大地推动了识字率的普及与科学技术的进步。然而，另一些人认为算法才是更关键的发展。
在十进制位值制普及之前，人们使用罗马数字。例如，1448 在罗马数字中写作 MCDXLVIII。用罗马数字进行加减法已经相当困难，乘除法更是极其复杂。古腾堡本人可能也只能用手指进行简单加减，复杂计算必须咨询算盘专家。
十进制位值制大约在公元 600 年左右起源于印度，仅用 10 个符号就能紧凑地表示任意大的数，并通过简单、机械的步骤高效地进行算术运算。然而，这一思想因语言、距离和愚昧的传统障碍而传播缓慢。
最具影响力的传播媒介是一本教科书：9 世纪时，一位住在巴格达的人——花拉子密（Al Khwarizmi）用阿拉伯语撰写了系统阐述加减乘除乃至开方、计算 π 的数位等基本方法的著作。这些过程精确、无歧义、机械、高效、正确——简而言之，它们就是算法（algorithm）。这个术语正是为了纪念这位智者，在十进制最终被欧洲采用后的许多世纪才被创造出来。
此后，十进制位值制及其数值算法在西方文明中扮演了巨大角色：它们推动了科学技术，加速了工业与商业。当计算机最终被设计出来时，它明确地将位值制体现在其比特、字和算术单元中。科学家们随后为各种问题开发了越来越复杂的算法，最终改变了世界。
花拉子密的著作之所以能在西方扎根，离不开一位 15 世纪意大利数学家莱昂纳多·斐波那契（Leonardo Fibonacci）的努力。他看到了位值制的潜力，致力于进一步发展并推广它。
但今天，斐波那契最广为人知的是一串著名的数列：
\[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, \ldots\]
其中每一项都是前两项之和。更正式地，斐波那契数 \(F_n\) 由以下简单规则生成：
\[ F_n = \begin{cases} F_{n-1} + F_{n-2} & \text{if } n > 1 \\ 1 & \text{if } n = 1 \\ 0 & \text{if } n = 0 \end{cases} \]
没有任何其他数列被如此广泛地研究，或被应用到如此多的领域：生物学、人口学、艺术、建筑、音乐，仅举几例。而且，与 2 的幂一起，它是计算机科学中最受欢迎的数列。
事实上，斐波那契数增长得几乎和 2 的幂一样快：例如，\(F_{30}\) 超过一百万，而 \(F_{100}\) 已经有 21 位数字！一般来说，\(F_n \approx 2^{0.694n}\)（见练习 0.3）。
但 \(F_{100}\) 或 \(F_{200}\) 的精确值是多少？斐波那契本人肯定想知道这些。为了回答这个问题，我们需要一个计算第 \(n\) 个斐波那契数的算法。
每当我们有一个算法时，我们总是要问三个问题： 1. 它正确吗？ 2. 它需要多少时间（作为 \(n\) 的函数）？ 3. 我们能做得更好吗？
一个直观的想法是直接按照 \(F_n\) 的递归定义来实现。以下是本书中使用的伪代码表示：
function fib1(n)
if n = 0: return 0
if n = 1: return 1
return fib1(n-1) + fib1(n-2)
正确性：这个算法的正确性不言自明，因为它正是斐波那契对 \(F_n\) 的定义。
时间分析：设 \(T(n)\) 为计算 fib1(n) 所需的计算机基本步骤数。对于较小的 \(n\)，过程几乎立即停止： \[ T(n) \leq 2 \quad \text{for } n \leq 1 \]
对于较大的 \(n\)，有两次递归调用，分别耗时 \(T(n-1)\) 和 \(T(n-2)\)，加上三个基本步骤（检查 \(n\) 的值和一次加法）： \[ T(n) = T(n-1) + T(n-2) + 3 \quad \text{for } n > 1 \]
将其与 \(F_n\) 的递推关系比较，我们立即看到 \(T(n) \geq F_n\)。这是非常坏的消息：算法的运行时间与斐波那契数一样快地增长！\(T(n)\) 是关于 \(n\) 的指数函数，这意味着该算法除了对非常小的 \(n\) 外，都慢得不切实际。
让我们更具体地看看指数时间有多糟糕。要计算 \(F_{200}\)，fib1 算法执行 \(T(200) \geq F_{200} \geq 2^{138}\) 个基本步骤。在地球上最快的计算机上，这仍然需要极长的时间——即使开始计算，也会远远超过太阳变成红巨星的时间。
技术在迅速改进——计算机速度大约每 18 个月翻一番，这一现象有时被称为摩尔定律。fib1(n) 的运行时间与 \(2^{0.694n} \approx (1.6)^n\) 成正比，因此计算 \(F_{n+1}\) 比计算 \(F_n\) 多花 1.6 倍的时间。而在摩尔定律下，计算机每年大约快 1.6 倍。所以如果我们今年能合理地计算 \(F_{100}\)，明年就能计算 \(F_{101}\)。后年，\(F_{102}\)。以此类推：每年只能多算一个斐波那契数！这就是指数时间的诅咒。
简而言之，我们的朴素递归算法是正确的，但低效得令人绝望。我们能做得更好吗？
让我们手算 fib1(5) 的递归调用树和步骤数。
fib1(5) 触发 fib1(4) 和 fib1(3)
fib1(4) 触发 fib1(3) 和 fib1(2)
fib1(3) 触发 fib1(2) 和 fib1(1)
fib1(2) 触发 fib1(1) 和 fib1(0) → 1, 0
fib1(1) → 1
fib1(2) 触发 fib1(1) 和 fib1(0) → 1, 0
fib1(3) 触发 fib1(2) 和 fib1(1)
fib1(2) 触发 fib1(1) 和 fib1(0) → 1, 0
fib1(1) → 1
可以看到 fib1(3) 被计算了 2 次，fib1(2) 被计算了 3 次。大量重复计算！
现在估算 T(5)：
T(0) ≤ 2, T(1) ≤ 2
T(2) = T(1) + T(0) + 3 ≤ 2 + 2 + 3 = 7
T(3) = T(2) + T(1) + 3 ≤ 7 + 2 + 3 = 12
T(4) = T(3) + T(2) + 3 ≤ 12 + 7 + 3 = 22
T(5) = T(4) + T(3) + 3 ≤ 22 + 12 + 3 = 37
而 \(F_5 = 5\)，确实 \(T(5) \geq F_5\)。随着 \(n\) 增大，\(T(n)\) 与 \(F_n\) 同步指数增长。
让我们理解为什么 fib1 如此缓慢。图 0.1 显示了单次调用 fib1(n) 触发的递归调用级联。注意到许多计算被重复了！更明智的方案是在中间结果一旦得知时就存储它们——即值 \(F_0, F_1, \ldots, F_{n-1}\)。
function fib2(n)
if n = 0 return 0
create an array f[0...n]
f[0] = 0, f[1] = 1
for i = 2 to n:
f[i] = f[i-1] + f[i-2]
return f[n]
正确性：与 fib1 一样，这个算法的正确性不言自明，因为它直接使用了 \(F_n\) 的定义。
时间分析：内层循环包含一个基本步骤，执行 \(n-1\) 次。因此 fib2 使用的基本步骤数关于 \(n\) 是线性的。
从指数到多项式，这是一个巨大的突破。现在计算 \(F_{200}\) 甚至 \(F_{20,000}\) 都是完全合理的。
正如我们在本书中将反复看到的，正确的算法能带来截然不同的结果。
让我们手算 fib2(6) 的数组填充过程：
初始化：f[0] = 0, f[1] = 1
i = 2: f[2] = f[1] + f[0] = 1 + 0 = 1
i = 3: f[3] = f[2] + f[1] = 1 + 1 = 2
i = 4: f[4] = f[3] + f[2] = 2 + 1 = 3
i = 5: f[5] = f[4] + f[3] = 3 + 2 = 5
i = 6: f[6] = f[5] + f[4] = 5 + 3 = 8
返回 f[6] = 8。
共执行了 5 次加法，即 \(n-1 = 5\) 次。没有重复计算，每个 \(F_i\) 只算一次。
在我们目前的讨论中，我们一直在计算每个算法执行的基本计算机步骤数，并将这些基本步骤视为花费恒定时间。这是一个非常有用的简化。毕竟，处理器的指令集包含各种基本原语——分支、存储到内存、比较数字、简单算术等等——与其区分这些基本操作，不如将它们归为一类更方便。
但回顾我们对斐波那契算法的处理，我们对“基本步骤”的定义过于宽松了。如果相加的是小数（比如 32 位整数），将加法视为单个计算机步骤是合理的。但第 \(n\) 个斐波那契数大约有 \(0.694n\) 位长，随着 \(n\) 增长，这远远超过 32。对任意大的数执行算术运算不可能在单个恒定时间内完成。我们需要审计之前的运行时间估计，使它们更诚实。
我们将在第 1 章看到，两个 \(n\) 位数的加法大约需要与 \(n\) 成正比的时间；如果你回想一下小学的逐位相加过程，这不难理解。因此，fib1 执行了大约 \(F_n\) 次加法，实际上使用的基本步骤数大约与 \(n \cdot F_n\) 成正比。同样，fib2 的步骤数与 \(n^2\) 成正比，仍然是关于 \(n\) 的多项式，因此指数级优于 fib1。这一修正并没有削弱我们的突破。
但能否比 fib2 更好？确实可以：见练习 0.4。
矩阵方法 fib3：将递推写成矩阵形式 \[ \begin{pmatrix} F_n \\ F_{n+1} \end{pmatrix} = \begin{pmatrix} 0 & 1 \\ 1 & 1 \end{pmatrix}^n \begin{pmatrix} F_0 \\ F_1 \end{pmatrix} \] 通过快速幂（如计算 \(X^8\) 只需 3 次乘法），可以在 \(O(\log n)\) 次矩阵乘法内完成。但代价是涉及大数乘法，且中间结果为 \(O(n)\) 位。若乘法耗时 \(M(n) = O(n^2)\)，则 fib3 的总时间为 \(O(M(n) \log n)\)。fib3 是否优于 fib2 取决于能否比 \(O(n^2)\) 更快地乘 \(n\) 位整数。
我们刚刚看到，运行时间分析中的草率会导致结果不可接受的不准确。但也存在相反的危险：过于精确也是可能的。有洞察力的分析基于正确的简化。
用基本计算机步骤数表示运行时间已经是一种简化。毕竟，一个步骤所花费的时间严重依赖于特定处理器，甚至依赖于缓存策略等细节。考虑这些架构特定的细节是一项噩梦般的复杂任务，并且产生的结果无法从一台计算机推广到另一台。
因此，寻求一种简洁的、机器无关的算法效率特征更有意义。为此，我们总是通过计算基本计算机步骤数来表示运行时间，作为输入大小的函数。
这种简化导致了另一个简化。与其报告一个算法在大小为 \(n\) 的输入上需要 \(5n^3 + 4n + 3\) 步，不如省略低阶项（如 \(4n\) 和 \(3\)，它们随着 \(n\) 增长变得不重要），甚至省略首项系数的细节（几年后计算机会快 5 倍），直接说算法花费时间 \(O(n^3)\)（读作“大 O of \(n^3\)”）。
定义：设 \(f(n)\) 和 \(g(n)\) 是从正整数到正实数的函数。我们说 \(f = O(g)\)（意思是“\(f\) 的增长速度不超过 \(g\)”），如果存在常数 \(c > 0\) 使得 \(f(n) \leq c \cdot g(n)\)。
说 \(f = O(g)\) 是“\(f \leq g\)”的一个非常宽松的类比。它与通常的 \(\leq\) 概念不同，因为有常数 \(c\)，例如 \(10n = O(n)\)。这个常数也允许我们忽略 \(n\) 较小时的情况。
例如，假设有两个算法：一个需要 \(f_1(n) = n^2\) 步，另一个需要 \(f_2(n) = 2n + 20\) 步。哪个更好？这取决于 \(n\)。对于 \(n \leq 5\)，\(f_1\) 较小；此后，\(f_2\) 明显胜出。在这种情况下，\(f_2\) 随 \(n\) 增长扩展得好得多，因此更优。
这种优越性被大 O 记号捕获：\(f_2 = O(f_1)\)，因为对所有 \(n\) 有 \[ \frac{f_2(n)}{f_1(n)} = \frac{2n + 20}{n^2} \leq 22 \] 另一方面，\(f_1 \neq O(f_2)\)，因为比值 \(f_1(n)/f_2(n) = n^2/(2n + 20)\) 可以任意大。
现在另一个算法来了，使用 \(f_3(n) = n + 1\) 步。这比 \(f_2\) 好吗？当然，但只是常数因子。\(f_2\) 和 \(f_3\) 之间的差异与 \(f_1\) 和 \(f_2\) 之间的巨大差距相比微不足道。为了专注于大局，我们将仅差乘法常数的函数视为等价。
回到大 O 的定义，我们看到 \(f_2 = O(f_3)\)： \[ \frac{f_2(n)}{f_3(n)} = \frac{2n + 20}{n + 1} \leq 20 \] 当然也有 \(f_3 = O(f_2)\)，此时 \(c = 1\)。
就像 \(O(\cdot)\) 是 \(\leq\) 的类比一样，我们也可以定义 \(\geq\) 和 \(=\) 的类比：
\(f = \Omega(g)\) 表示 \(g = O(f)\)
\(f = \Theta(g)\) 表示 \(f = O(g)\) 且 \(f = \Omega(g)\)
大 O 记号让我们专注于大局。面对像 \(3n^2 + 4n + 5\) 这样的复杂函数，我们只需用 \(O(f(n))\) 替换它，其中 \(f(n)\) 尽可能简单。在这个例子中我们会用 \(O(n^2)\)，因为二次部分主导了其余部分。以下是一些帮助通过省略被主导项来化简函数的常识规则：
证明 \(f(n) = 3n^2 + 4n + 5\) 是 \(O(n^2)\)、\(\Omega(n^2)\)，因此是 \(\Theta(n^2)\)。
证明 \(f = O(n^2)\)： 对于所有 \(n \geq 1\)，有 \(4n \leq 4n^2\) 和 \(5 \leq 5n^2\)。因此 \[ f(n) = 3n^2 + 4n + 5 \leq 3n^2 + 4n^2 + 5n^2 = 12n^2 \] 取 \(c = 12\)，即满足定义，故 \(f = O(n^2)\)。
证明 \(f = \Omega(n^2)\)： 对于所有 \(n \geq 0\)，有 \(4n + 5 \geq 0\)。因此 \[ f(n) = 3n^2 + 4n + 5 \geq 3n^2 \] 取 \(c = 3\)，即 \(f(n) \geq 3n^2\)，故 \(f = \Omega(n^2)\)。
综上，\(f = \Theta(n^2)\)。
fib1 的正确性没有问题，它是斐波那契定义的直接翻译；问题不在于正确性，而在于效率太低，时间复杂度是指数级的
大 O 记号中的常数 c 只是缩放因子，不改变增长阶；例如 10n = O(n)，因为 10n ≤ 10·n 对所有 n 成立
fib3 的乘法次数是 O(log n)，但每次乘法涉及 O(n) 位的大数，若乘法本身耗时 M(n)，则总时间为 O(M(n) log n)，不一定优于 fib2 的 O(n²)
即使最快的计算机，fib1(200) 也需要极长时间；摩尔定律每年只能让计算机多算一个斐波那契数，指数时间算法无法通过硬件升级解决
从算术步骤看 fib2 是 O(n)，但从位运算看每次加法耗时 O(n)，总复杂度为 O(n²)，不过仍是多项式时间，远优于 fib1 的指数时间
问题：关于 fib1 算法的时间复杂度，下列哪项最准确？
问题：关于动态规划算法 fib2，下列哪项正确？
问题：大 O 记号中，f(n) = 3n² + 4n + 5 可以简化为？
问题：关于矩阵法 fib3，下列哪项正确？
lectures/chap0.pdf · p. 11-12 · confidence: high · Al Khwarizmi laid out the basic methods for adding, multiplying... they were algorithms, a term coined to honor the wise manlectures/chap0.pdf · p. 12-13 · confidence: high · T(n) = T(n-1) + T(n-2) + 3 for n > 1. Compare this to the recurrence relation for F_n: we immediately see that T(n) ≥ F_nlectures/chap0.pdf · p. 13-14 · confidence: high · The inner loop consists of a single computer step and is executed n-1 times. Therefore the number of computer steps used by fib2 is linear in nlectures/chap0.pdf · p. 15-16 · confidence: high · We say f = O(g) if there is a constant c > 0 such that f(n) ≤ c·g(n)