Commit dc0d499

当我们试图通过执行时间来表征算法的效率时，并且独立于任何特定程序或计算机，重要的是量化算法需要的操作或者步骤的数量。选择适当的基本计算单位是个复杂的问题，并且将取决于如何实现算法。对于先前的求和算法，一个比较好的基本计算单位是对执行语句进行计数。在 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 变大时，如果没有它，我们的近似也是准确的。

另外一个示例，假设对于一些算法，确定的步数是 $T(n)=5n^2+27n+1005$。当 n 很小时, 例如 1 或 2 ，常数 1005 似乎是函数的主要部分。然而，随着 n 变大，$n^2$ 这项变得越来越重要。事实上，当 n 真的很大时，其他两项在它们确定最终结果中所起的作用变得不重要。当 n 变大时，为了近似 T(n)，我们可以忽略其他项，只关注 $5n^2$ 。系数 5 也变得不重要。我们说，T(n) 具有的数量级为 $f(n)=n^2$。 或者 $O( n^2 )$ 。

分配操作数分为四个项的总和。第一个项是常数 3, 表示片段开始的三个赋值语句。第二项是 $3n^2$, 因为由于嵌套迭代，有三个语句执行 $n^2$ 次。第三项是 2n, 两个语句迭代 n 次。最后，第四项是常数 1，表示最终赋值语句。最后得出 $T(n)=3+3n^2+2n+1=3n^2+2n+4$，通过查看指数，我们可以看到 $n^2$ 项是显性的，因此这个代码段是 $O(n^ 2)$。当 n 增大时，所有其他项以及主项上的系数都可以忽略。

当 n 变大，$n^2$ 这项占据主导，1/2 可以忽略。所以这个算法复杂度为 $O(n^2)$。

首先你可能认为这个算法是 $O(n)$，因为只有一个简单的迭代来比较排序后的 n 个字符。但是，调用 Python 排序不是没有成本。正如我们将在后面的章节中看到的，排序通常是 $O(n^2)$ 或 $O(nlogn)$。所以排序操作比迭代花费更多。最后该算法跟排序过程有同样的量级。

解决这类问题的强力方法是穷举所有可能性。对于乱序检测，我们可以生成 s1 的所有乱序字符串列表，然后查看是不是有 s2。这种方法有一点困难。当 s1 生成所有可能的字符串时，第一个位置有 n 种可能，第二个位置有 n-1 种，第三个位置有 n-3 种，等等。总数为 $n*(n-1)*(n-2)*...*3*2*1$， 即 n!。虽然一些字符串可能是重复的，程序也不可能提前知道这样，所以他仍然会生成 n! 个字符串。

同样，这个方案有多个迭代，但是和第一个解法不一样，它不是嵌套的。两个迭代都是 n, 第三个迭代，比较两个计数列表，需要 26 步，因为有 26 个字母。一共 `T(n)=2n+26`，即 $O(n)$，我们找到了一个线性量级的算法解决这个问题。

两个常见的操作是索引和分配到索引位置。无论列表有多大，这两个操作都需要相同的时间。当这样的操作和列表的大小无关时，它们是 $O(1)$。

另一个非常常见的编程任务是增加一个列表。有两种方法可以创建更长的列表，可以使用 append 方法或拼接运算符。append 方法是 $O(1)$。 然而，拼接运算符是 $O(k)$，其中 k 是要拼接的列表的大小。这对你来说很重要，因为它可以帮助你通过选择合适的工具来提高你自己的程序的效率。

现在我们已经看到了如何具体测试性能，见 Table2, 你可能想知道 pop 两个不同的时间。当列表末尾调用 pop 时，它需要 $O(1)$, 但是当在列表中第一个元素或者中间任何地方调用 pop, 它是 $O(n)$。原因在于 Python 实现列表的方式，当一个项从列表前面取出，列表中的其他元素靠近起始位置移动一个位置。你会看到索引操作为 $O(1)$。python的实现者会权衡选择一个好的方案。

Figure 3 展示了我们实验的结果，你可以看到，随着列表变长，pop(0) 时间也增加，而 pop() 时间保持非常平坦。这正是我们期望看到的 $O(n)$ 和 $O(1)$。

我们会在最后的实验中，将比较列表和字典之间的 contains 操作的性能。在此过程中，我们将确认列表的 contains 操作符是 $O(n)$，字典的 contains 操作符是 $O(1)$。我们将在实验中列出一系列数字。然后随机选择数字，并检查数字是否在列表中。如果我们的性能表是正确的，列表越大，确定列表中是否包含任意一个数字应该花费的时间越长。

Figure 4 展示了 Listing6 的结果。你可以看到字典一直更快。 对于最小的列表大小为10,000个元素，字典是列表的89.4倍。对于最大的列表大小为990,000 个元素。字典是列表的11,603倍！你还可以看到列表上的contains运算符所花费的时间与列表的大小成线性增长。这验证了列表上的contains运算符是 $O(n)$ 的断言。还可以看出，字典中的 contains 运算符的时间是恒定的，即使字典大小不断增长。事实上，对于字典大小为10,000个元素，contains操作占用0.004毫秒，对于字典大小为990,000个元素，它也占用0.004毫秒。