* 回顾计算机科学的思想, 提高编程和解决问题的 能力。

之前，我们将过程抽象称为隐藏特定函数的细节的过程，以允许用户或客户端在高层查看它。我们现在将注意力转向类似的思想，即数据抽象的思想。`抽象数据类型`（有时缩写为 ADT ）是对我们如何查看数据和允许的操作的逻辑描述，而不y用考虑如何实现它们。这意味着我们只关心数据表示什么，而不关心它最终将如何构造。通过提供这种级别的抽象，我们围绕数据创建一个封装。通过封装实现细节，我们将它们从用户的视图中隐藏。这称为信息隐藏。

Figure 2 展示了抽象数据类型是什么以及如何操作。用户与接口交互，使用抽象数据类型指定的操作。抽象数据类型是用户与之交互的 shell。实现是隐藏在更深的底层。用户不关心实现的细节。

计算机科学家通过经验学习。我们通过看别人解决问题和自己解决问题来学习。接触不同的问题解决技术，看不同的算法设计有助于我们承担下一个具有挑战性的问题。通过思考许多不同的算法，我们可以开始开发模式识别，以便下一次出现类似的问题时，我们能够更好地解决它。

先前我们提出一个问题是哪个函数更好，答案取决于你的标准。如果你关注可读性，函数 sumOfN 肯定比 foo 好。事实上，你可能已经在你介绍编程的课程中看到过很多例子，他们的目标之一就是帮助你编写易于阅读和理解的程序。在本课程中，我们对如何表示算法感兴趣（当然我们希望你继续努力编写可读的，易于理解的代码）。

算法分析涉及基于每个算法使用的计算资源量来比较算法。我们比较两个算法，说一个比另一个算法好的原因在于它在使用资源方面更有效率，或者仅仅使用的资源更少。从这个角度来看，上面两个函数看起来很相似。它们都使用基本相同的算法来求解问题。在这点上，更重要的是我们如何考虑真正意义上的计算资源。有两个方法，一种是考虑算法所需的空间或者内存。所需的空间通常由问题本身决定。但是，算法会有一些特殊的空间需求，我们可以细细观察解释这些变动。

Listing 1 嵌入了时间函数，函数返回一个包含结果和消耗时间的数组。如果我们 执行这个函数 5 次，每次计算前 10,000 个整数的和，将得到一下结果：

如果我们对 sumOfN3 做同样的基准测试，使用 5 个不同的 n(10,000, 100,000, 1,000,000, 100,000,000), 我们得到如下结果

有两点关注下，首先上面记录的时间比上面任何例子都短， 另外他们的时间和 n 无关， 看来 sumOfN3 几乎不受 n 的影响。

但是这个基准测试告诉我们什么？我们可以直观的看到用迭代的方案在做更多的工作，因为一些步骤重复。这可能是它需要更长时间的原因。此外，迭代所需时间随着 n 递增。还有个问题，如果我们在不同计算机上或者使用不用的编程语言运行这个函数，我们也可能得到不同的结果。如果用老计算机，可能需要更长时间才能执行完 sumOfN3。

当我们试图通过执行时间来表征算法的效率时，并且独立于任何特定程序或计算机，重要的是量化算法需要的操作或者步骤的数量。选择适当的基本计算单位是个复杂的问题，并且将取决于如何实现算法。对于先前的求和算法，一个比较好的基本计算单位是对执行语句进行计数。在 sumOfN 中，赋值语句的计数为 1 (\(theSum = 0\)) 加上 n 的值（我们执行 \(theSum=theSum+i\) 的次数）。我们通过函数 T 表示 \(T(n)=1 + n\)。参数 n 通常称为‘问题的规模’，我们称作 ‘T(n) 是解决问题大小为 n 所花费的时间，即 1+n 步长’。在上面的求和函数中，使用 n 来表示问题大小是有意义的。我们可以说，100,000 个整数和比 1000 个问题规模大。因此，所需时间也更长。我们的目标是表示出算法的执行时间是如何相对问题规模大小而改变的。

计算机科学家更喜欢将这种分析技术进一步。事实证明，操作步骤数量不如确定 \(T(n)\) 最主要的部分来的重要。换句话说，当问题规模变大时， \(T(n)\) 函数某些部分的分量会超过其他部分。函数的数量级表示了随着 n 的值增加而增加最快的那些部分。数量级通常称为大O符号，并写为 \(O(f(n))\)。它表示对计算中的实际步数的近似。函数 \(f(n)\) 提供了 \(T(n)\) 最主要部分的表示方法。

在上述示例中，\(T(n)=1+n\)。当 n 变大时，常熟 1 对于最终结果变得越来越不重要。如果我们找的是 \(T(n)\) 的近似值，我们可以删除 1， 运行时间是\(O(n)\)。要注意，1 对于 \(T(n)\) 肯定是重要的。但是当 n 变大时，如果没有它，我们的近似也是准确的。