<<<<<<< HEAD

在上述示例中，`T(n)=1+n`。当 n 变大时，常熟 1 对于最终结果变得越来越不重要。如果我们找的是 \(T(n)\) 的近似值，我们可以删除 1， 运行时间是\(O(n)\)。要注意，1 对于 \(T(n)\) 肯定是重要的。但是当 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 ) 。

虽然我们没有在求和示例中看到这一点，但有时算法的性能取决于数据的确切值，而不是问题规模的大小。对于这种类型的算法，我们需要根据最佳情况，最坏情况或平均情况来表征它们的性能。最坏情况是指算法性能特别差的特定数据集。而相同的算法不同数据集可能具有非常好的性能。大多数情况下，算法执行效率处在两个极端之间（平均情况）。对于计算机科学家而已，重要的是了解这些区别，使它们不被某一个特定的情况误导。

Figure 1 表示了 Table 1 中的函数图。注意，当 n 很小时，函数彼此间不是很好的定义。很难判断哪个是主导的。随着 n 的增长，就有一个很明确的关系，很容易看出它们之间的大小关系。

分配操作数分为四个项的总和。第一个项是常数 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 增大时，所有其他项以及主项上的系数都可以忽略。

Figure 2 展示了一些常用的 大O 函数，跟上面讨论的 T(n) 函数比较，一开始的时候，T(n) 大于 三次函数，后来随着 n 的增长，三次函数超过了 T(n)。T(n) 随着二次函数继续增长。

我们对回文问题的第一个解法是检查第一个字符串是不是出现在第二个字符串中。如果可以检验到每一个字符，那两个字符串一定是回文。可以通过用 None 替换字符来完成检查。但是，由于 Python 字符串是不可变的，所以第一步是将第二个字符串转换为列表。第一个字符串中的每个字符可以通过检查在第二个列表中检查元素是否存在，如果存在，替换成None。见 ActiveCode1

为了分析这个算法，我们注意到 s1 的每个字符都会在 s2 进行最多 n 个字符的迭代。列表中的 n 个位置将被访问一次来匹配来自 s1 的字符。访问次数可以写成 1 到 n 整数的和，可以写成

另一个解决方案是利用这么一个事实，即使 s1,s2 不同，它们只有由完全相同的字符组成，它们才是回文。所以，如果我们按照字母顺序排列每个字符串，从 a 到 z, 如果两个字符串相同，则这两个字符串为回文。见 ActiveCode2。

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

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

事实证明，n! 比 n^2 增长还快，事实上，如果 s1 有 20个字符长，则将有 20! = 2,432,902,008,176,640,000 个字符串产生。如果我们每秒处理一种可能字符串，那么需要 77,146,816,596 才能过完整个列表。所以这不是很好的解决方案。

我们最终解决回文的方法是利用两个回文字符串具有相同的 a, b, c等等的事实。我们首先计算的是每个字母出现的次数。由于有 26 个可能的字符，我们就用 26 个列表，每个可能的字符一个。每次看到一个特定的字符，就增加该位置的计数器。最后如果两个列表的计数器一样，则字符串为回文字符串。见 ActiveCode 3

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

要使用 timeit，您需要创建一个 Timer 对象，其参数是两个 Python 语句。第一个参数是一个你想要执行时间的 Python 语句; 第二个参数是一个将运行一次以设置测试的语句。然后 timeit 模块将计算执行语句所需的时间。默认情况下，timeit 将尝试运行语句一百万次。 当它完成时，它返回时间作为表示总秒数的浮点值。由于它执行语句一百万次，可以读取结果作为执行测试一次的微秒数。你还可以传递 timeit 一个参数名字为 number，允许您指定执行测试语句的次数。以下显示了运行我们的每个测试功能 1000 次需要多长时间。

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

作为一种演示性能差异的方法，我们用 timeit 来做一个实验。我们的目标是验证从列表从末尾 pop 元素和从开始 pop 元素的性能。同样，我们也想测量不同列表大小对这个时间的影响。我们期望看到的是，从列表末尾处弹出所需时间将保持不变，即使列表不断增长。而从列表开始出弹出元素时间将随列表增长而增加。

Listing 4 展示了两种 pop 方式的比较。从第一个示例看书，从末尾弹出需要 0.0003 毫秒。从开始弹出要花费 4.82毫秒。对于一个 200万的元素列表，相差 16000 倍。

Listing 4 需要注意的几点，第一， `from __main__ import x` , 虽然我们没有定义一个函数，我们确实希望能够在我们的测试中使用列表对象 x, 这种方法允许我们只计算单个弹出语句，获得该操作最精确的测量时间。因为 timer 重复了 1000 次，所以该列表每次循环大小都减1。但是由于初始列表大小为 200万，我们只减少总体大小的 0.05%。

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