第 3 课 导言

CS61AS 第 3 课导言：介绍空间、时间与树形递归，探讨程序资源管理。

资源与计算

计算机很强大，但它们有其极限。正因如此，程序员工作的一部分就是高效地管理计算机的资源——如果程序员写出的程序效率太低，计算机就会在试图执行它的过程中耗尽资源。程序效率低下主要有两大类：空间与时间。空间（space）是计算机执行一个程序所需的「草稿纸」数量；时间（time）则是计算机运行完一个程序所需的时长。在接下来的几节中，我们将详细考察这两个维度。

首先，我们来看空间。一个低效的程序可能占用过多空间而无法运行，导致计算机崩溃。我们将研究造成这一问题的原因，以及如何通过一种特殊的递归——尾递归（tail recursion）——来避免它。

接着，我们考虑时间。有些程序的运行时间可能比宇宙的寿命还要长。（例如，我们已知的寻找国际象棋完美解的最佳程序就是如此。）我们将学习如何识别这类程序，并更一般地介绍、练习一种衡量程序时间效率的方法。

最后，我们还将介绍另一种新的递归类型——树形递归（tree recursion）。在程序中使用树形递归，我们就能应对此前没有工具可解的问题。我们将特别关注这项新技术带来的代价与收益。

阅读材料

你可以查阅教材和课堂讲义中的补充阅读材料。每一节都附有更具体的教材链接，遇到不清楚的地方可以查阅。