用Python解决数据结构与算法问题（二）：算法分析

python学习之路 - 从入门到精通到大师

〇、写在前面

来晚了来晚了，上一篇 用Python解决数据结构与算法问题（一）：Python基础 的反应不错，也有同学觉得难，其实这是正常的，类的部分无论在哪一个语言中都是难点，慢慢来吧。

之所以这么久才出第二篇，不是因为打磨了特别久，而是因为最近一直在忙课题，忙着炼丹，结果还出了各种问题，有点方，所以可能有时候会拖更一下下，有啥问题还是留言吧。好了，闲话少说，开始第二节。

一、什么是算法分析

一个很普遍的现象是，很多刚接触 IT 的学生，在编程解决问题之后，会将自己的程序和其他人的相比较，想看一下哪一个程序 better，比如你在 LeetCode 或者 牛客网 做题的时候。其实大部分人会比较疑惑，这些程序或者说代码，看起来都很相似，或者相差甚远（简单的程序可能会相似得多），那么，当两个程序解决同样的问题，但是看起来不同时，Which is better than the others？（哪一个比别的更好？）

为了回答这个问题，需要记住一件事，程序 和 程序代表的底层算法 之间是存在重要的区别的。

• 一方面，一种算法是一个通用的、逐步解决某种问题的指令列表。它是用于解决一种问题的任何实例的方法，即给定特定输入，产生期望的结果。
• 另一方面，程序是使用某种编程语言编码的算法。根据程序员和他们所使用的编程语言的不同，可能存在描述相同算法的许多不同的程序。

想要进一步探讨这种差异，请参考下面代码中的函数 sumOfN，这个函数解决了一个我们熟悉的问题——计算前 n 个整数的和。

def sumOfN(n):
    theSum = 0
    for i in range(1,n+1):
        theSum = theSum + i

    return theSum

print(sumOfN(10))

该算法使用初始化值为 0 的 累加器（accumulator） 变量，然后迭代 n 个整数，将每个依次添加到累加器，最后输出累加器变量的值，即我们期望求得的结果。

现在再来看看下面代码中的函数 foo。乍一看，你可能会觉得它有点奇怪，但是如果耐着性子进一步地观察，可以看到这个函数本质上和前一个函数没什么区别，换句话说其实是在做着同样的事情。。。。。。

def foo(tom):
    fred = 0
    for bill in range(1,tom+1):
        barney = bill
        fred = fred + barney

    return fred

print(foo(10))

为什么这个函数这么不直观？原因在于编码习惯不好，其实在 【记录】一个深度学习计算机视觉(CV)算法工程师的成长之路（思考和方法以及计划） 中我们提到过，这不只是针对 深度学习CV算法工程师 而言，是针对所有编程人员而言的，要有一个良好的编程习惯。

原文如下：

因为没有使用良好的 标识符（identifier） 名称来提升可读性，此外还在迭代步骤中使用了一个额外的赋值语句，这并不是真正必要的，综上两个原因，导致在粗读代码时，完全 get 不到代码的含义，搞出个笑话来。

先前我们曾提出一个问题——哪一个函数更好？其实答案取决于你的标准。

• 如果你关注 可读性，函数 sumOfN 肯定比函数 foo 好。
• 如果你关注 功能性，函数 sumOfN 和函数 foo 是没什么大的区别的。
• 如果你关注 计算性，函数 sumOfN 还是比函数 foo 好，马上会讲到原因。

事实上，如果你看过类似的课程或者书籍，那么很有可能已经看到过很多例子了，你应该知道他们的目标之一就是帮助你编写易于阅读和理解的程序！！！

回到正题上来，什么是算法分析？

算法分析是基于每种算法使用的计算资源量来比较算法，即 计算性。所以如果我们要比较两个算法，说一个比另一个算法好，那么原因应该在于，好的算法在使用资源方面更有效率，或者仅仅使用的资源更少。很明显，功能相同，函数 foo 的代码要更多，自然就不如函数 sumOfN 好。在 计算性 这点上，重要的是要更多地考虑真正意义上的计算资源，有两种方法：

• 一种是考虑算法解决问题所需的空间或者内存；
• 一种是考虑算法解决问题所需的时间，是空间需求的一种替代方法。

解决方案所需的空间通常由问题本身决定，但是，有时候某些算法也会有一些特殊的空间需求，这种情况下要非常仔细地注意这些变动。

算法执行所需的时间，有时被称为算法的 执行时间 或 运行时间，可以通过 基准分析（benchmark analysis） 来测量函数的执行时间，比如之前定义的函数 SumOfN 。这意味着我们将记录程序计算出结果所需的实际时间，这个实现很简单，在 Python 中，通过记录相对于系统的开始时间和结束时间来对函数进行 基准测试。

在 time 模块中有一个 time 函数，它可以在任意被调用的地方返回系统时钟的当前时间（以秒为单位）。通过在开始和结束的时候分别调用两次 time 函数，然后计算差异，就可以得到一个函数执行花费的精确秒数（大多数情况下是这样）。代码如下：

import time

def sumOfN2(n):
    start = time.time()

    theSum = 0
    for i in range(1,n+1):
        theSum = theSum + i

    end = time.time()

    return theSum, end-start

在上面的代码中，我们嵌入了时间函数，函数返回一个包含了执行结果和执行消耗时间的元组（用Python解决数据结构与算法问题（一）：Python基础）。如果执行这个函数 5 次，每次计算前 10,000 个整数的和，将得到如下结果：

>>>for i in range(5):
       print("Sum is %d required %10.7f seconds"%sumOfN2(10000))
       
Sum is 50005000 required  0.0000000 seconds
Sum is 50005000 required  0.0009995 seconds
Sum is 50005000 required  0.0000000 seconds
Sum is 50005000 required  0.0009956 seconds
Sum is 50005000 required  0.0000000 seconds

可以发现时间是相当一致的，执行这段代码平均需要0.0003990秒，那么如果运行计算前 100,000 个整数的和的函数呢？

>>>for i in range(5):
       print("Sum is %d required %10.7f seconds"%sumOfN2(100000))
       
Sum is 5000050000 required  0.0039890 seconds
Sum is 5000050000 required  0.0049868 seconds
Sum is 5000050000 required  0.0049601 seconds
Sum is 5000050000 required  0.0040183 seconds
Sum is 5000050000 required  0.0049844 seconds

再次的，尽管时间更长，但每次运行所需的时间也是非常一致的，平均需要0.0045877秒，大约是10倍（非要严格计算的话是11倍）。

而对于 n 等于 1,000,000，得到：

>>>for i in range(5):
       print("Sum is %d required %10.7f seconds"%sumOfN2(1000000))
       
Sum is 500000500000 required  0.0488636 seconds
Sum is 500000500000 required  0.0478487 seconds
Sum is 500000500000 required  0.0488696 seconds
Sum is 500000500000 required  0.0488698 seconds
Sum is 500000500000 required  0.0488687 seconds

在这种情况下，尽管时间增加了很多，但每次运行所需的时间还是非常一致的，平均需要0.0486641秒，大约是前一次的10倍。

好了，先把这几个结果放在一边，来考虑一下下面的代码，它显示了求解求和问题的不同方法。

def sumOfN3(n):
   return (n*(n+1))/2

print(sumOfN3(10))

如果你还记得数学上的求和公式的话，就知道函数 sumOfN3 利用自然数的求和公式而不是迭代来计算前n个整数的和。

$\sum_{i=1}^n i=\frac{(n)(n+1)}{2}$

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

import time

def sumOfN3(n):
    start = time.time()

    theSum = (n*(n+1))/2

    end = time.time()

    return theSum, end-start

print("Sum is %d required %10.7f seconds"%sumOfN3(10000))
print("Sum is %d required %10.7f seconds"%sumOfN3(100000))
print("Sum is %d required %10.7f seconds"%sumOfN3(1000000))
print("Sum is %d required %10.7f seconds"%sumOfN3(10000000))
print("Sum is %d required %10.7f seconds"%sumOfN3(100000000))

在这个代码的输出结果中，有两点需要重点关注，首先是记录的代码执行时间比之前任何例子都短；另外执行时间和 n 无关，函数 sumOfN3 几乎不受 n 的影响。但是这个 基准测试 能告诉我们什么？可以直观地看到使用了迭代的解决方案需要做更多的工作，因为一些程序步骤被重复执行，这可能是它需要更长时间的原因。此外，迭代方案执行所需时间是随着 n 递增的。另外还有一个设备的问题，如果在不同计算机上或者使用不用的编程语言运行这个函数，也可能得到不同的结果。

综上所述，得出一个结论，需要一个更好的方法来描述 这些算法的执行时间。基准测试 计算的是程序执行的实际时间，它并不真正地提供给我们一个有用的 度量（measurement），来判断到底哪个程序更佳，或者更 match 我们的问题。因为它取决于特定的机器，程序，时间，编译器和编程语言，这些都可以影响最后的结果。

记得之前在慕课上参与过一个讨论，论题是：

我通过查阅资料和自己理解，得出的答案。

这确实是一个很大的问题。相反地说，我们希望或者说迫切需要有一个独立于所使用的程序或计算机的 度量，这个 度量 将有助于独立地判断算法，并且可以用于比较不同实现方法的算法的效率，那么这个 度量 将会更加公正，或者说是可信度更高。

二、大 O 符号表示法的出现

在《算法图解》的笔记（《算法图解》学习笔记（一）：二分查找（附代码））中说过它，它就是，，，对，就是它——大 O 表示法。

当我们试图通过 执行时间 来表征算法的效率时，并且独立于任何特定程序或计算机，重要的是量化算法 需要的操作 或者 步骤的数量。这么看来的话，选择一个适当的基本计算单位是个及其复杂的问题，并且将取决于如何实现这个算法。对于先前的求和算法，一个比较好的基本计算单位是对执行语句进行计数，比如在 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 变大时，即使没有它，近似结果也是比较准确的。举个例子，假设 n=10，那么 n+1=11；但是当 n=10000 时，n+1=10001，看起来即使没了这个1，也就没有特别得了；那么如果 n=100000000 时，n+1=100000001，这时候去掉 1 就是基本零影响的了，你懂了吗？

在求和示例中可以看到一点，有时 算法性能 取决于 数据的确切值，而不是 问题规模 的大小，比如上面例子中，n=1 和 n=100000000 就完全不一样，当然我这里是夸张的手法。对于这种类型的算法，往往需要根据 最佳情况、最坏情况 或 平均情况 这三个方面来表征它们的 性能。

• 最坏情况 是指让 算法性能 特别差的特定数据集；
• 而针对相同的算法在不同数据集上可能具有非常好的性能，即 最佳情况。
• 大多数情况下，算法执行效率是处在两个极端之间的，即 平均情况。

不要只看一种情况，不要被某一个特定的情况误导，因为那都是片面的，就像数数也会多数几次，来看一下准不准确！

当学习算法分析时，一些常见的数量级函数将会反复出现，如下表：

为了确定这些函数中哪个是最主要的部分，我们需要看到当 n 变大的时候它们如何相互比较的。注意，当 n 很小时，函数彼此间不能很好的定义，很难判断哪个是主导的；而随着 n 的增长，就有一个很明确的关系，很容易看出它们之间的大小关系。

其实如果你细心的话，就知道表格从上到下，依次是复杂度增加的情况，这样在算法分析时，你就能准确的得到最终的结论了。简单举个例子， $O(N)$ 和 $O(logN)$，根据图中的结论， $O(N)$ > $O(logN)$，后者要更简单一下。

最后来看一个实际的例子，假设代码如下：

def sum(n):
    for i in range(1, n):
        a = 3
        b = 3 * i * i
        c = 2 * i
        d = 1
        x = a + b + c + d
        A = a / x
        B = b / x
        C = c / x
        D = d / x
    return A, B, C, D


print("当n=10，a 项的比重：%.3f,b 项的比重：%.3f,c 项的比重：%.3f,d 项的比重：%.3f" % sum(10))
print("当n=100000，a 项的比重：%.3f,b 项的比重：%.3f,c 项的比重：%.3f,d 项的比重：%.3f" % sum(100000))

分配操作数分为四个项的总和：

• 第一项是常数 $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 增大时，所有其他项以及主项上的系数都可以忽略。很明显，代码的输出结果也是这个结论，我们通过把每一项除以综合进行一个比重的计算，可以发现 $b$ 这一项的比重要更高，尤其是当 n 增加到很大的时候！！！甚至到了 1。

上图展示了上面讨论的 $T(n)$ 函数和一些常用的大 O 函数的比较情况。一开始的时候， $T(n)$ 大于三次函数（三次函数起始比较小，越小就越小，越大就越大），后来随着 n 的增长，三次函数超过了 $T(n)$， $T(n)$ 随着二次函数继续增长了，即 $O(n^ 2)$。

三、一个乱序字符串检查的例子

这个图，我鸡皮疙瘩起来了。。。总之就是混乱的意思。

显示不同量级的算法的一个很好的例子就是——字符串的乱序检查。乱序字符串是指一个字符串是另一个字符串的重新排列，也就是元素相同但是排列顺序不同。例如，'heart' 和 'earth' 就是乱序字符串；'python' 和 'typhon' 也是。为了简单起见，假设所讨论的两个字符串具有相等的长度，并且由 26 个小写字母集合组成，而目标是写一个布尔函数，它将两个字符串做参数并返回它们是不是乱序。

总计四种解法，现在开始了。

3.1、解法1 - 检查

对乱序问题的第一个解法是检查第一个字符串是不是出现在第二个字符串中。

如果可以检验到每一个字符，那这两个字符串一定是乱序，可以通过用 None 替换字符来了解一个字符是否完成检查。但是，由于 Python 字符串是不可变的，所以第一步是将第二个字符串转换为列表，检查第一个字符串中的每个字符是否存在于第二个列表中，如果存在，替换成 None。

def anagramSolution1(s1, s2):
	# 字符串不可变，为了标记已经检测到的，转换成列表
    alist = list(s2)

    pos1 = 0
    stillOK = True

    while pos1 < len(s1) and stillOK:
        pos2 = 0
        found = False
        while pos2 < len(alist) and not found:
            if s1[pos1] == alist[pos2]:
                found = True
            else:
                pos2 = pos2 + 1

		# 对检测到的字符标记None
        if found:
            alist[pos2] = None
            pos1 = pos1 + 1
        else:
            stillOK = False

    return stillOK and (len(list(filter(None, alist))) == 0)


print(anagramSolution1('abcd', 'dcba'))

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

$\sum_{i=1}^n i=\frac{ n(n+1) }{2}=\frac{1}{2}n^2+\frac{1}{2}n$

当 n 变大， $n^2$ 这项占据主导，1/2 可以忽略，所以这个算法复杂度为 $O(n^2)$，或者你也可以仿照之前的比重方式，自己改写代码。

3.2、解法2 - 排序和比较

这个算法的想法是这样的，即使 s1,s2 不同，它们都是由完全相同的字符组成的，所以按照字母顺序从 a 到 z 进行排列，如果两个字符串完全相同，那这就是乱序字符串。

def anagramSolution2(s1, s2):
	# 用列表的排序方法
    alist1 = list(s1)
    alist2 = list(s2)

    alist1.sort()
    alist2.sort()

    pos = 0
    matches = True

    while pos < len(s1) and matches:
        if alist1[pos] == alist2[pos]:
            pos = pos + 1
        else:
            matches = False

    return matches


print(anagramSolution2('abcde', 'edcba'))

首先因为只有一个简单的迭代来比较排序后的 n 个字符，所以你可能认为这个算法是 $O(n)$。但是我这么说就说明肯定是没这么简单的，要知道 调用 Python 排序不是没有成本。不要因为现在的上层如此发达，就以为整个过程就是这么简答的，之前还有个小伙伴和我说，调用一下就出来了，怎么调用的？ 后面的章节中会讲到，排序通常是 $O(n^2)$ 或 $O(nlogn)$，所以排序操作比迭代花费更多，最后该算法跟排序过程有同样的量级， $n$ 相对较小被忽略了。

3.3、解法3 - 穷举法

解决这类问题的强力方法是穷举所有可能性，讲道理，如果这个世界不在意成本什么的，穷举是无敌的。。。

对于 乱序检测，可以生成 s1 的所有可能乱序字符串的列表，然后查看其中是不是有 s2。这种方法有一点困难，困难在哪？ 就在成本！当 s1 生成所有可能的字符串时，第一个位置有 n 种可能，第二个位置有 n-1 种，第三个位置有 n-2 种，…等等。总数为

$n*(n-1)*(n-2)*...*3*2*1$

即 n!。虽然一些字符串可能是重复的，程序也不可能提前知道这样，所以它就一直跑，仍然会生成 n! 个字符串。

事实证明，n! 比 $n^2$ 增长还快，假设 s1 有 20 个字符长，则 20! = 2432902008176640000，而 $20^2=400$，相差甚远。。。如果每秒处理一种可能字符串，那么需要 77146816596 年才能处理完整个列表，所以很明显这不是一个好的解决方案，因为成本限制了你。

from itertools import permutations
import time
import matplotlib.pyplot as plt
 
 
def judge(s1, s2):
    s2Per = permutations(s2)
    for i in s2Per:
        if s1 == i:
            break
 
 
timesum = []
N = 14
 
for len in range(1, N):
    start = time.perf_counter()
    s1 = [str(x) for x in range(10, 10 + len)]
    s2 = [str(x) for x in range(len)]
    judge(s1, s2)
    timesum.append(time.perf_counter() - start)
    print("变位词长度：{}，运行时间：{}".format(len, time.perf_counter() - start))
plt.plot(range(1, N), timesum)
plt.show()

3.4、解法4 - 计数和比较

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

def anagramSolution4(s1, s2):
    c1 = [0] * 26
    c2 = [0] * 26

    for i in range(len(s1)):
        pos = ord(s1[i]) - ord('a')
        c1[pos] = c1[pos] + 1

    for i in range(len(s2)):
        pos = ord(s2[i]) - ord('a')
        c2[pos] = c2[pos] + 1

    j = 0
    stillOK = True
    while j < 26 and stillOK:
        if c1[j] == c2[j]:
            j = j + 1
        else:
            stillOK = False

    return stillOK


print(anagramSolution4('apple', 'pleap'))

你会说迭代也很多啊，是的，这个方案也有多个迭代，但是和第一个解法不一样，它的迭代不是嵌套的，而是并列的，这就意味在求大 O 的时候是相加关系，而大 O 是只看数量级的，所以相加等于对大 O 结果是没啥影响的。两个迭代都是 n, 第三个迭代，比较两个计数列表，需要 26 步，因为有 26 个字母，一共是 T(n)=2n+26，即 $O(n)$，也就是 linear，我们找到了一个线性量级的算法解决这个问题。

小结：

• 第一种解决方法：检查、 $O(n^2)$；
• 第二种解决方法：排序和比较、 $O(n^2)$ 或 $O(nlogn)$；
• 第三种解决方法：穷举法、 $O(n!)$；
• 第四种解决方法：计数、 $O(n)$；

在结束这个例子之前，来讨论下空间花费，虽然最后一个方案在线性时间执行，但它需要额外的存储来保存两个字符计数列表，换句话说，就是牺牲了空间以获得时间，简称空间换时间。不要觉得总能找到一种兼得的方法，鱼和熊掌不可兼得也，要么空间，要么时间，很多情况下，你需要做出权衡。在这个例子下，额外空间不重要，但是如果有数百万个字符，就需要关注下，因为这就重要了。

四、算法分析之列表二三事

上一讲简单地讲了一些列表操作（https://blog.csdn.net/TeFuirnever/article/details/101673308#21_94），没看的小伙伴建议看一下。

python 的设计者在实现列表数据结构的时候有很多选择，每一个这种选择都可能影响列表操作的性能。为了做出正确的选择，他们查看了 最常用的 列表数据结构，并且优化了实现，以便这个号称 最常见的 操作非常快。当然，他们还试图使较不常见的操作也非常快，但是当需要做出折中的时候，较不常见的操作的性能通常牺牲以支持 更常见的 操作。

两个 常见的 操作是 索引 和 分配到索引位置，无论列表有多大，这两个操作都需要相同的时间。当这样的操作和列表的大小无关时，它们是 $O(1)$。还有一个 非常常见的 编程任务是 增加一个列表。有两种方法可以创建更长的列表——append 方法或拼接运算符。

• append 方法是 $O(1)$。
• 拼接运算符是 $O(k)$，其中 k 是要拼接的列表大小。

这些对你来说很重要，因为它们可以帮你通过选择合适的工具来提高程序的效率。来看看下面四种不同的【生成一个从0开始的n个数字的列表】的方式：

• 首先，尝试一个 for 循环并通过创建列表；
• 然后，使用 append 而不是拼接；
• 接下来，使用列表生成器创建列表；
• 最后，也是最明显的方式，通过调用列表构造函数包装 range 函数。

def test1():
    l = []
    for i in range(1000):
        l = l + [i]

def test2():
    l = []
    for i in range(1000):
        l.append(i)

def test3():
    l = [i for i in range(1000)]

def test4():
    l = list(range(1000))

想要捕获每个函数的执行时间，使用 Python 的 timeit 模块。

timeit 模块旨在允许 Python 开发人员通过在一致的环境中运行函数并使用尽可能相似的操作系统的时序机制来进行跨平台时序测量。

要使用 timeit，需要创建一个 Timer 对象，其参数是两个 Python 语句：

• 第一个参数是一个想要执行时间的 Python 语句；
• 第二个参数是一个将运行一次以设置测试的语句。

然后 timeit 模块将计算执行语句所需的时间。默认情况下，timeit 将尝试运行语句一百万次，当完成时，返回时间作为表示总秒数的浮点值。由于它执行语句一百万次，可以读取结果作为执行测试一次的微秒数，因而还可以传递 timeit 一个参数名字为 number，允许指定执行测试语句的次数。

以下显示了运行每个测试功能 1000 次需要多长时间：

import timeit


def test1():
    l = []
    for i in range(1000):
        l = l + [i]


def test2():
    l = []
    for i in range(1000):
        l.append(i)


def test3():
    l = [i for i in range(1000)]


def test4():
    l = list(range(1000))


t1 = timeit.Timer("test1()", "from __main__ import test1")
print("concat ", t1.timeit(number=1000), "milliseconds")

t2 = timeit.Timer("test2()", "from __main__ import test2")
print("append ", t2.timeit(number=1000), "milliseconds")

t3 = timeit.Timer("test3()", "from __main__ import test3")
print("comprehension ", t3.timeit(number=1000), "milliseconds")

t4 = timeit.Timer("test4()", "from __main__ import test4")
print("list range ", t4.timeit(number=1000), "milliseconds")

从上面的实验可以清楚地看出，append 操作比 concat 操作快得多，1.08 >> 0.06。

在上面的例子中，对 test1(), test2() 等的函数调用计时，setup 语句可能看起来很奇怪，所以详细说一下：
 
你可能非常熟悉 from ,import 语句，但这通常用在 python 程序文件的开头。在这种情况下，from __main__ import test1 从 __main__ 命名空间导入到 timeit 设置的命名空间中，timeit 这么做是因为它想在一个干净的环境中做测试，而不会因为可能有创建的任何杂变量，以一种不可预见的方式干扰函数的性能。

上面看到的时间其实都包括实际调用函数的一些开销的，但我们可以假设函数调用开销在四种情况下是相同的，所以这个比较仍然是有意义的。但是，拼接字符串操作需要 1.08 毫秒的结果并不准确，而是拼接字符串这个函数需要 1.08 毫秒，如果想知道准确结果，可以测试调用空函数所需要的时间，并从上面的数字中减去它，交给你了。

现在已经看到了如何具体测试性能，见下表。

发现有两个 pop，你可能想知道 pop 为啥有两个不同的时间。当列表末尾调用 pop 时，它需要 $O(1)$，但是当在列表中第一个元素或者中间任何地方调用 pop，它是 $O(n)$，原因在于 Python 实现列表的方式。当一个项从列表前面取出，列表中的其他元素会向起始位置移动一个位置，而索引操作为 $O(1)$，python的实现者权衡选择其中一个好的方案。

现在我们验证列表从末尾 pop 元素和从开始 pop 元素的性能。同样，我们也想测量不同列表大小对这个时间的影响。我们期望看到的是：

• 从列表末尾处弹出所需时间将保持不变，即使列表不断增长；
• 从列表开始处弹出元素时间将随列表增长而增加。

从示例中可以看出，从末尾弹出需要 0.000073 毫秒。从开始弹出要花费 2.092254 毫秒。对于一个 200 万的元素列表来说，二者相差将近 3 万倍。

import timeit

popzero = timeit.Timer("x.pop(0)",
                       "from __main__ import x")

popend = timeit.Timer("x.pop()",
                      "from __main__ import x")

x = list(range(2000000))
print(popzero.timeit(number=1000))

x = list(range(2000000))
print(popend.timeit(number=1000))

虽然测试显示 pop(0) 比 pop() 慢， 但它没有证明 pop(0) 是 $O(n)$，pop() 是 $O(1)$。要验证它，需要看下一系列列表大小的调用效果。

import timeit
import matplotlib.pyplot as plt

popzero = timeit.Timer("x.pop(0)",
                       "from __main__ import x")

popend = timeit.Timer("x.pop()",
                      "from __main__ import x")

print("        pop(0)           pop()")

pt_sum = []
pz_sum = []

for i in range(1000000, 100000001, 1000000):
    x = list(range(i))
    pt = popend.timeit(number=1000)
    pt_sum.append(pt)
    x = list(range(i))
    pz = popzero.timeit(number=1000)
    pz_sum.append(pz)
    print("%15.5f, %15.5f" % (pz, pt))


plt.plot(range(1000000, 100000001, 1000000), pt_sum, label='pop(0)')
plt.plot(range(1000000, 100000001, 1000000), pz_sum, label='pop()')
plt.legend()
plt.show()

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

五、算法分析之字典二三事

python 中第二个主要的数据结构是字典。你可能记得，字典和列表不同，可以通过键而不是位置来访问字典中的项目。

字典的 get 和 set 操作都是 $O(1)$；另一个重要的操作是 contains，检查一个键是否在字典中也是 $O(1)$。所有字典操作的效率总结在下表中：

关于字典性能的一个重要方面是，表中提供的效率是针对 平均性能。 在一些罕见的情况下，contains，get item 和 set item 操作可以退化为 $O(n)$，后面会有介绍。

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

注意，对容器中的数字执行完全相同的操作，唯一的区别在于在第 7 行上 x 是一个列表，第 9 行上的 x 是一个字典。

import timeit
import matplotlib.pyplot as plt
import random

lst_sum = []
d_sum = []


for i in range(10000, 1000001, 20000):
    t = timeit.Timer("random.randrange(%d) in x" % i,
                     "from __main__ import random,x")
    x = list(range(i))
    lst_time = t.timeit(number=1000)
    lst_sum.append(lst_time)
    x = {j: None for j in range(i)}
    d_time = t.timeit(number=1000)
    d_sum.append(d_time)
    print("%d,%10.3f,%10.3f" % (i, lst_time, d_time))


plt.plot(range(10000, 1000001, 20000), lst_sum, label='list')
plt.plot(range(10000, 1000001, 20000), d_sum, label='dict')
plt.legend()
plt.show()

下图展示了实验的结果，可以看到字典一直更快。

• 对于最小的列表大小为 10000 个元素，字典是列表的 89.4 倍；
• 对于最大的列表大小为 990000 个元素，字典是列表的 11603 倍！

还可以看到列表上的 contains 运算符所花费的时间与列表的大小成线性增长，这验证了列表上的 contains 运算符是 $O(n)$ 的断言。除此之外，还可以看出，字典中的 contains 运算符的时间是恒定的，即使字典大小不断增长。事实上，对于字典大小为 10000 个元素，contains 操作占用 0.004 毫秒，对于字典大小为 990000 个元素，它也占用 0.004 毫秒，是 $O(1)$。

由于 Python 是一种不断发展的语言，底层总是有变化的。 有关 Python 数据结构性能的最新信息可以在 Python 网站上找到。 在撰写本文时，Python wiki 有一个很好的时间复杂性页面，可以在 Time Complexity Wiki 中找到。

六、总结

• 算法分析是一种独立的测量算法的方法。
• 大O表示法允许根据问题的大小，通过其主要部分来对算法进行分类。

参考文章

• 《problem solving with algorithms and data structure using python》
• https://github.com/facert/python-data-structure-cn

转载：https://blog.csdn.net/TeFuirnever/article/details/101941843