第2章：算法分析

发表于 | 更新于 | 分类于
本文字数： 15k | 阅读时长 ≈ 14 分钟

思考并回答以下问题：

本章目标

  • 理解算法分析的重要性。
  • 能够使用大O符号描述执行时间。
  • 针对Python列表和字典的常见操作，理解用大O符号表示的执行时间。
  • 理解Python数据的实现如何影响算法分析。
  • 理解如何对简单的Python程序进行基准测试。

何谓算法分析

刚接触计算机科学的同学常常拿自己的程序和别人的做比较。你可能已经注意到了，计算机程序看起来很相似，尤其是简单的程序。这就产生了一个有趣的问题：当两个看上去不同的程序解决同一个问题时，会有优劣之分么？

要回答这个问题，需要记住，程序和它所代表的算法是不同的。第1章说过，算法是为逐步解决问题而设计的一系列通用指令。给定某个输入，算法能得到对应的结果——算法就是解决问题的方法。程序则是用某种编程语言对算法编码。同一个算法可以对应许多程序，这取决于程序员和编程语言。

为了进一步说明算法和程序的区别，来看看代码清单2-1中的函数。该函数解决了一个常见的问题，即计算前n个整数之和。算法的思路是使用一个初始值为0的累加器变量，然后遍历n个整数，并将值加到累加器上。

代码清单2-1 计算前n个整数之和

1
2
3
4
5
6
def sumOfN(n):
    theSum = 0
    for i in range(1, n+1):
        theSum = theSum + i

    return theSum

下面看看代码清单2-2。乍看会觉得有些奇怪，但是仔细观察后，你会发现这个函数所做的工作在本质上和前一个相同。之所以不能一眼看出来，是因为代码写得太差。没有用好的变量名提高可读性，而且在累加时还使用了一条多余的赋值语句。

代码清单2-2 计算前n个整数之和的另一种写法

1
2
3
4
5
6
7
def foo(tom):
    fred = 0
    for bill in range(1, tom+1):
        barney = bill
        fred = fred + barney

    return fred

前面提出过一个问题：程序是否有优劣之分？答案取决于你的标准。如果你关心的是可读性，那么sumOfN当然比foo更好。实际上，你可能已经在编程入门课上看过很多例子，毕竟入门课的一个目标就是帮你写出易读的程序。不过，除了可读性，本书还对描述算法感兴趣。（我们当然希望你继续向着写出易读代码的目标努力。）

算法分析关心的是基于所使用的计算资源比较算法。我们说甲算法比乙算法好，依据是甲算法有更高的资源利用率或使用更少的资源。从这个角度来看，上面两个函数其实差不多，它们本质上都利用同一个算法解决累加问题。

计算资源究竟指什么？思考这个问题很重要。有两种思考方式。一是考虑算法在解决问题时要占用的空间或内存。解决方案所需的空间总量一般由问题实例本身决定，但算法往往也会有特定的空间需求，后文会详细介绍。

另一种思考方式是根据算法执行所需的时间进行分析和比较。这个指标有时称作算法的执行时间或运行时间。要衡量sumOfN函数的执行时间，一个方法就是做基准分析。也就是说，我们会记录程序计算出结果所消耗的实际时间。在Python中，我们记录下函数就所处系统而言的开始时间和结束时间。time模块中有一个time函数，它会以秒为单位返回自指定时间点起到当前的系统时钟时间。在首尾各调用一次这个函数，计算差值，就可以得到以秒为单位的执行时间（多数情况下非常短）。

在代码清单2-3中，sumOfN函数在累加前后调用time。函数返回一个元组，由结果与计算时间（单位为秒）构成。如果调用5次，每次计算前10 000个整数之和，会得到如下结果。

1
2
3
4
5
6
7
8
>>> for i in range(5):
        print("Sum is %d required %10.7f seconds" % sumOfN(10000))
Sum is 50005000 required  0.0018950 seconds
Sum is 50005000 required  0.0018620 seconds
Sum is 50005000 required  0.0019171 seconds
Sum is 50005000 required  0.0019162 seconds
Sum is 50005000 required  0.0019360 seconds
>>>

代码清单2-3 计算执行时间

1
2
3
4
5
6
7
8
9
10
11
12
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

可以看出，执行时间基本上是一致的，平均约为0.0019秒。如果计算前100 000个整数之和，又会如何呢？

1
2
3
4
5
6
7
8
>>> for i in range(5):
        print("Sum is %d required %10.7f seconds" % sumOfN(100000))
Sum is 5000050000 required  0.0199420 seconds
Sum is 5000050000 required  0.0180972 seconds
Sum is 5000050000 required  0.0194821 seconds
Sum is 5000050000 required  0.0178988 seconds
Sum is 5000050000 required  0.0188949 seconds
>>>

执行时间都变长了，但还是很一致，差不多都是之前的10倍。如果n取1 000 000，结果如下。

1
2
3
4
5
6
7
8
>>> for i in range(5):
        print("Sum is %d required %10.7f seconds" % sumOfN(1000000))
Sum is 500000500000 required  0.1948988 seconds
Sum is 500000500000 required  0.1850290 seconds
Sum is 500000500000 required  0.1809771 seconds
Sum is 500000500000 required  0.1729250 seconds
Sum is 500000500000 required  0.1646299 seconds
>>>

这次的平均执行时间差不多是前一个例子的10倍。

现在来看看代码清单2-4，其中给出了解决累加问题的新方法。函数sumOfN3使用以下公式计算前n个整数之和，不必使用循环。

代码清单2-4 不使用循环来计算前n个整数之和

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

对sumOfN3做同样的基准测试，n取5个值（10 000、100 000、1 000 000、10 000 000和100 000 000），会得到以下结果。

1
2
3
4
5
Sum is 50005000 required 0.00000095 seconds
Sum is 5000050000 required 0.00000191 seconds
Sum is 500000500000 required 0.00000095 seconds
Sum is 50000005000000 required 0.00000095 seconds
Sum is 5000000050000000 required 0.00000119 seconds

关于这个结果，有两点要注意。首先，记录的耗时比之前的例子都要短。其次，不管n取什么值，耗时都很稳定。看起来sumOfN3不太受整数数目的影响。

不过，以上基准测试结果的意义到底是什么呢？直觉上，循环方案看上去工作量更大，因为有些步骤重复。这好像是耗时更久的原因。而且，循环方案的耗时会随着n一起增长。然而，这里有个问题。如果在另一台计算机上运行这个函数，或用另一种编程语言来实现，很可能会得到不同的结果。如果计算机再旧些，sumOfN3的执行时间甚至更长。

所以，我们需要更好的方式来描述算法的执行时间。基准测试计算的是执行算法的实际时间。这不是一个有用的指标，因为它依赖于特定的计算机、程序、时间、编译器与编程语言。我们希望找到一个独立于程序或计算机的指标。这样的指标在评价算法方面会更有用，可以用来比较不同实现下的算法。

大O记法

试图摆脱程序或计算机的影响而描述算法的效率时，量化算法的操作或步骤很重要。如果将每一步看成基本计算单位，那么可以将算法的执行时间描述成解决问题所需的步骤数。确定合适的基本计算单位很复杂，也依赖于算法的实现。

对于累加算法，计算总和所用的赋值语句的数目就是一个很好的基本计算单位。在sumOfN函数中，赋值语句数是1（theSum = 0）加上n（theSum = theSum + i的运行次数）。可以将其定义成函数$T$，令$T(n)=1+n$。参数n常被称作问题规模，可以将函数解读为“当问题规模为n时，解决问题所需的时间是$T(n)$，即需要$1+n$步”。

在前面给出的累加函数中，用累加次数定义问题规模是合理的。这样一来，就可以说处理前100 000个整数的问题规模比处理前1000个整数的大。鉴于此，前者花的时间要比后者长。接下来的目标就是揭示算法的执行时间如何随问题规模而变化。

计算机科学家将分析向前推进了一步。精确的步骤数并没有$T(n)$函数中起决定性作用的部分重要。也就是说，随着问题规模的增长，$T(n)$函数的某一部分会比其余部分增长得更快。最后比较的其实就是这一起决定性作用的部分。数量级函数描述的就是，当n增长时，$T(n)$增长最快的部分。数量级（order of magnitude）常被称作大$\boldsymbol{O}$记法（O指order），记作$O(f(n))$。它提供了步骤数的一个有用的近似方法。$f(n)$函数为$T(n)$函数中起决定性作用的部分提供了简单的表示。

对于$T(n)=1+n$，随着n越来越大，常数1对最终结果的影响越来越小。如果要给出$T(n)$的近似值，可以舍去1，直接说执行时间是$O(n)$。注意，1对于$T(n)$来说是重要的。但是随着n的增长，没有1也不会太影响近似值。

再举个例子，假设某算法的步骤数是$T(n)=5n^2+27n+1005$。当n很小时，比如说1或2，常数1005看起来是这个函数中起决定性作用的部分。然而，随n着增长，$n^2$变得更重要。实际上，当n很大时，另两项的作用对于最终结果来说就不显著了，因此可以忽略这两项，只关注$5n^2$。另外，当n变大时，系数5的作用也不显著了。因此可以说，函数$T(n)$的数量级是$f(n)=n^2$，或者直接说是$O(n^2)$。

累加的例子没有体现的一点是，算法的性能有时不仅依赖于问题规模，还依赖于数据值。对于这种算法，要用最坏情况、最好情况和普通情况来描述性能。最坏情况指的是某一个数据集会让算法的性能极差；另一个数据集可能会让同一个算法的性能极好（最好情况）。大部分情况下，算法的性能介于两个极端之间（普通情况）。计算机科学家要理解这些区别，以免被某个特例误导。

在学习算法的路上，常见的函数会反复出现，如表2-1所示。要判断哪一个才是$T(n)$的决定性部分，必须了解它们在n变大时彼此有多大差别。图2-1展示了表2-1中的各个函数。注意，当n较小时，这些函数之间的界限不是很明确，很难看出哪个起主导作用。随着n的增长，它们之间的差别就很明显了。

表2-1 常见的大$\boldsymbol{O}$函数

$\boldsymbol{f(n)}$
名称
$1$ 常数
$\log n$ 对数
$n$ 线性
$n\log n$ 对数线性
$n^2$ 平方
$n^3$ 立方
$2^n$ 指数

图2-1 常见的大O函数

最后来看一个例子，假设有如代码清单2-5所示的一段Python代码。尽管这个程序没有做什么实际工作，但它对分析性能有一定的指导意义。

代码清单2-5 Python代码示例

1
2
3
4
5
6
7
8
9
10
11
12
a = 5
b = 6
c = 10
for i in range(n):
    for j in range(n):
        x = i * i
        y = j * j
        z = i * j
for k in range(n):
    w = a * k + 45
    v = b * b
d = 33

赋值操作的数量是4项之和：$T(n)=3+3n^2+2n+1$。第1项是常数3，对应起始部分的3条赋值语句。第2项是$3n^2$，因为有3条语句要在嵌套循环中重复$n^2$次。第3项是$2n$，因为两条语句要循环n遍。第4项是常数1，代表最后那条赋值语句。

很容易看出来，$n^2$起主导作用，所以这段代码的时间复杂度是$O(n^2)$。当n变大时，其他项以及主导项的系数都可以忽略。

图2-2展示了一部分常见的大O函数与前面讨论的$T(n)$函数的对比情况。注意，$T(n)$一开始比立方函数大。然而，随着n的增长，立方函数很快就超越了$T(n)$。

图2-2 对比$T(n)$函数与常见的大O函数

异序词检测示例

要展示不同数量级的算法，一个好例子就是经典的异序词检测问题。如果一个字符串只是重排了另一个字符串的字符，那么这个字符串就是另一个的异序词，比如heart与earth，以及python与typhon。为了简化问题，假设要检查的两个字符串长度相同，并且都是由26个英文字母的小写形式组成的。我们的目标是编写一个布尔函数，它接受两个字符串，并能判断它们是否为异序词。

方案1：清点法

清点第1个字符串的每个字符，看看它们是否都出现在第2个字符串中。如果是，那么两个字符串必然是异序词。清点是通过用Python中的特殊值None取代字符来实现的。但是，因为Python中的字符串是不可修改的，所以先要将第2个字符串转换成列表。在字符列表中检查第1个字符串中的每个字符，如果找到了，就替换掉。代码清单2-6给出了这个函数。

代码清单2-6 实现清点方案

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
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

        if found:
            alist[pos2] = None
        else:
            stillOK = False

        pos1 = pos1 + 1

    return stillOK

来分析这个算法。注意，对于s1中的n个字符，检查每一个时都要遍历s2中的n个字符。要匹配s1中的一个字符，列表中的n个位置都要被访问一次。因此，访问次数就成了从1到n的整数之和。这可以用以下公式来表示。

当n变大时，起决定性作用的是$n^2$，而$\frac{1}{2}$可以忽略。所以，这个方案的时间复杂度是$O(n^2)$。

方案2：排序法

尽管s1与s2是不同的字符串，但只要由相同的字符构成，它们就是异序词。基于这一点，可以采用另一个方案。如果按照字母表顺序给字符排序，异序词得到的结果将是同一个字符串。代码清单2-7给出了这个方案的实现代码。在Python中，可以先将字符串转换为列表，然后使用内建的sort方法对列表排序。

代码清单2-7 实现排序方案

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
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

乍看之下，你可能会认为这个算法的时间复杂度是$O(n)$，因为在排序之后只需要遍历一次就可以比较$n$个字符。但是，调用两次sort方法不是没有代价。我们在后面会看到，排序的时间复杂度基本上是$O(n^2)$或$O(n\log n)$，所以排序操作起主导作用。也就是说，该算法和排序过程的数量级相同。

方案3：蛮力法

用蛮力解决问题的方法基本上就是穷尽所有的可能。就异序词检测问题而言，可以用s1中的字符生成所有可能的字符串，看看s2是否在其中。但这个方法有个难处。用s1中的字符生成所有可能的字符串时，第1个字符有n种可能，第2个字符有$n-1$种可能，第3个字符有$n-2$种可能，依此类推。字符串的总数是$n*(n-1)*(n-2)*\cdots*3*2*1$，即$n!$。也许有些字符串会重复，但程序无法预见，所以肯定会生成$n!$个字符串

n当较大时，$n!$增长得比$2^n$还要快。实际上，如果s1有20个字符，那么字符串的个数就是$20!=2~432~902~008~176~640~000$。假设每秒处理一个，处理完整个列表要花77 146 816 596年。这可不是个好方案。

方案4：计数法

最后一个方案基于这样一个事实：两个异序词有同样数目的a、同样数目的b、同样数目的c，等等。要判断两个字符串是否为异序词，先数一下每个字符出现的次数。因为字符可能有26种，所以使用26个计数器，对应每个字符。每遇到一个字符，就将对应的计数器加1。最后，如果两个计数器列表相同，那么两个字符串肯定是异序词。代码清单2-8给出了这个方案的实现代码。

代码清单2-8 实现计数方案

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
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

这个方案也有循环。但不同于方案1，这个方案的循环没有嵌套。前两个计数循环都是n阶的。第3个循环比较两个列表，由于可能有26种字符，因此会循环26次。全部加起来，得到总步骤数$T(n)=2n+26$，即$O(n)$。我们找到了解决异序词检测问题的线性阶算法。

结束这个例子的讲解之前，需要聊聊空间需求。尽管方案4的执行时间是线性的，它还是要用额外的空间来存储计数器。也就是说，这个算法用空间换来了时间。

这种情形很常见。很多时候，都需要在时间和空间之间进行权衡。本例中，额外使用的空间并不大。不过，如果有数以百万计的字符，那就有问题了。面对多种算法和具体的问题，计算机科学家需要决定如何利用好计算资源。

Python数据结构的性能

你对大O记法及其不同函数的差别已经有了大致的了解。本节的目标是针对Python的列表和字典介绍如何用大O记法描述操作的性能。我们会做一些实验，展示在每个数据结构上做某些操作时的损耗与收益。理解这些Python数据结构的效率很重要，因为它们是本书用来实现其他数据结构的基石。本节不会解释性能优劣的原因。在后续章节中，你会看到列表和字典的一些可能的实现，以及为何性能取决于实现。

列表

在实现列表数据结构时，Python的设计师有许多选择，每一个选择都会影响操作的性能。为了做出正确的选择，他们考虑了列表最常见的用法，并据此优化列表的实现，以使最常用的操作非常快。当然，他们也尽力使不常用的操作也很快，但在需要权衡时，往往会牺牲低频操作的性能。

两个常见操作是索引和给某个位置赋值。无论列表多长，这两个操作所花的时间应该恒定。像这种与列表长度无关的操作就是常数阶的。

另一个常见的操作是加长列表。有两种方式：要么采用追加方法，要么执行连接操作。追加方法是常数阶的。如果待连接列表的长度为k，那么连接操作的时间复杂度就是$O(k)$。知道这一点很重要，因为它能帮你选择正确的工具，使程序更高效。

假设要从0开始生成含有n个数的列表，来看看4种生成方式。首先，用for循环通过连接操作创建列表；其次，采用追加方法；再次，使用列表解析式；最后，用列表构造器调用range函数（这可能是最容易想到的方式）。代码清单2-9给出了4种方式的代码。假设代码保存在文件listfuns.py中。

代码清单2-9 生成列表的4种方式

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
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模块。该模块使Python开发人员能够在一致的环境下运行函数，并且在多种操作系统下使用尽可能相似的机制，以实现跨平台计时。

要使用timeit模块，首先创建一个Timer对象，其参数是两条Python语句。第1个参数是要为之计时的Python语句；第2个参数是建立测试的语句。timeit模块会统计多次执行语句要用多久。默认情况下，timeit会执行100万次语句，并在完成后返回一个浮点数格式的秒数。不过，既然这是执行100万次所用的秒数，就可以把结果视作执行1次所用的微秒数。此外，可以给timeit传入参数number，以指定语句的执行次数。下面的例子展示了测试函数各运行1000次所花的时间。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
t1 = Timer("test1()", "from __main__ import test1")
print("concat ", t1.timeit(number=1000), "milliseconds")

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

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

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

# concat  6.54352807999 milliseconds
# append  0.306292057037 milliseconds
# comprehension  0.147661924362 milliseconds
# list range  0.0655000209808 milliseconds

在本例中，计时的语句是对test1()、test2()等的函数调用。你也许会觉得建立测试的语句有些奇怪，所以我们仔细研究一下。你可能已经熟悉from和import，但它们通常在Python程序文件的开头使用。本例中，from __main__ import test1将test1函数从__main__命名空间导入到timeit设置计时的命名空间。timeit模块这么做，是为了在一个干净的环境中运行计时测试，以免某些变量以某种意外的方式干扰函数的性能。

实验结果清楚地表明，0.30毫秒的追加操作远快于6.54毫秒的连接操作。实验也测试了另两种列表创建操作：使用列表解析式，以及使用列表构造器调用range。有趣的是，与用for循环进行追加操作相比，使用列表解析式几乎快一倍。

关于这个小实验要说明的最后一点是，执行时间其实包含了调用测试函数的额外开销，但可以假设4种情形的函数调用开销相同，所以对比操作还是有意义的。鉴于此，说连接操作花了6.54毫秒不太准确，应该说用于连接操作的测试函数花了6.54毫秒。可以做个练习，测一下调用空函数的时间，然后从之前得到的数字中减去。

知道如何衡量性能之后，可以对照表2-2，看看基本列表操作的大O效率。仔细考虑之后，你可能会对pop的两种效率有疑问。在列表末尾调用pop时，操作是常数阶的，在列表头一个元素或中间某处调用pop时，则是阶的。原因在于Python对列表的实现方式。在Python中，从列表头拿走一个元素，其他元素都要向列表头挪一位。你可能觉得这个做法有点傻，但再看看表2-2，你会明白这种实现保证了索引操作为常数阶。Python的实现者认为这是不错的取舍决策。

表2-2 Python列表操作的大$\boldsymbol{O}$效率

操作
大$\boldsymbol{O}$效率
索引 $O(1)$
索引赋值 $O(1)$
追加 $O(1)$
pop() $O(1)$
pop(i) $O(n)$
insert(i, item) $O(n)$
删除 $O(n)$
遍历 $O(n)$
包含 $O(n)$
切片 $O(k)$
删除切片 $O(n)$
设置切片 $O(n+k)$
反转 $O(n)$
连接 $O(k)$
排序 $O(n\log n)$
乘法 $O(nk)$

为了展示pop()和pop(i)的性能差异，我们使用timeit模块做另一个实验。实验目标是针对一个长度已知的列表，分别从列表头和列表尾弹出一个元素。我们也想衡量不同长度下的执行时间。预期结果是，从列表尾弹出元素的时间是恒定的，而从列表头弹出元素的时间会随着列表变长而增加。

代码清单2-10是实验代码。可以看到，从列表尾弹出元素花了0.0003毫秒，从列表头弹出花了4.8214毫秒。对于含有200万个元素的列表来说，后者是前者的16 000倍。

有两点需要说明。首先是from __main__ import x语句。尽管没有定义一个函数，但是我们仍然希望能在测试中使用列表对象x。这个办法允许我们只对pop语句计时，从而准确地获得这一个操作的耗时。其次，因为计时重复了1000次，所以列表每次循环都少一个元素。不过，由于列表的初始长度是200万，因此对于整体长度来说，只减少了0.05%。

代码清单2-10 pop的性能分析

1
2
3
4
5
6
7
8
9
10
popzero = timeit.Timer("x.pop(0)", "from __main__ import x")
popend = timeit.Timer("x.pop()", "from __main__ import x")

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

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

虽然测试结果说明pop(0)确实比pop()慢，但是并没有证明pop(0)的时间复杂度是$O(n)$，也没有证明pop()的是$O(1)$。要证明这一点，需要看看两个操作在各个列表长度下的性能。代码清单2-11实现了这个测试。

代码清单2-11 比较pop(0)和pop()在不同列表长度下的性能

1
2
3
4
5
6
7
8
9
popzero = Timer("x.pop(0)", "from __main__ import x")
popend = Timer("x.pop()", "from __main__ import x")
print("pop(0) pop()")
for i in range(1000000, 100000001, 1000000):
    x = list(range(i))
    pt = popend.timeit(number=1000)
    x = list(range(i))
    pz = popzero.timeit(number=1000)
    print("%15.5f, %15.5f" % (pz, pt))

图2-3展示了实验结果。可以看出，列表越长，pop(0)的耗时也随之变长，而pop()的耗时很稳定。这刚好符合$O(n)$和$O(1)$的特征。

图2-3 对比pop(0)和pop()的性能

实验会有一些误差。因为用来测量的计算机运行着其他进程，所以可能拖慢代码的速度。因此，尽管我们尽力减少计算机所做的其他工作，测出的时间仍然会有些许变化。这也是测试1000遍的原因，从统计角度来说，收集足够多的信息有助于得到可靠的结果。

字典

Python的第二大数据结构就是字典。你可能还记得，字典不同于列表的地方在于，可以通过键——而不是位置——访问元素。你会在后文中发现，实现字典有许多方法。现在最重要的是，知道字典的取值操作和赋值操作都是常数阶。另一个重要的字典操作就是包含（检查某个键是否在字典中），它也是常数阶。表2-3总结了所有字典操作的大O效率。要注意，表中给出的效率针对的是普通情况。在某些特殊情况下，包含、取值、赋值等操作的时间复杂度可能变成$O(n)$。后文在讨论不同的字典实现方式时会详细说明。

表2-3 Python字典操作的大$\boldsymbol{O}$效率

操作
大$\boldsymbol{O}$效率
复制 $O(n)$
取值 $O(1)$
赋值 $O(1)$
删除 $O(1)$
包含 $O(1)$
遍历 $O(n)$

最后一个性能实验会比较列表和字典的包含操作，并验证列表的包含操作是$O(n)$，而字典的是$O(1)$。实验很简单，首先创建一个包含一些数的列表，然后随机取一些数，看看它们是否在列表中。如果表2-2给出的效率是正确的，那么随着列表变长，判断一个数是否在列表中所花的时间也就越长。

对于以数字为键的字典，重复上述实验。我们会看到，判断数字是否在字典中的操作，不仅快得多，而且当字典变大时，耗时基本不变。

代码清单2-12实现了这个对比实验。注意，我们进行的是完全相同的操作。不同点在于，第7行的x是列表，第9行的x则是字典。

代码清单2-12 比较列表和字典的包含操作

1
2
3
4
5
6
7
8
9
10
import timeit
import random

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)
    x = {j:None for j in range(i)}
    d_time = t.timeit(number=1000)
    print("%d, %10.3f, %10.3f" % (i, lst_time, d_time))

图2-4展示了运行结果。可以看出，字典一直更快。对于元素最少的情况（10 000），字典的速度是列表的89.4倍。对于元素最多的情况（990 000），字典的速度是列表的11 603倍！还可以看出，随着规模增加，列表的包含操作在耗时上的增长是线性的，这符合$O(n)$。对于字典来说，即使规模增加，包含操作的耗时也是恒定的。实际上，当字典有10 000个元素时，包含操作的耗时是0.004毫秒，当有990 000个元素时，耗时还是0.004毫秒。

图2-4 比较列表和字典的包含操作

小结

  • 算法分析是一种独立于实现的算法度量方法。
  • 大O记法使得算法可以根据随问题规模增长而起主导作用的部分进行归类。

关键术语

大记法 对数 对数线性
蛮力法 平方 普通情况
清点法 时间复杂度 数量级
线性 指数 最坏情况

讨论题

给出以下代码的大O性能。

1
2
3
for i in range(n):
    for j in range(n):
        k = 2 + 2

给出以下代码的大O性能。

1
2
for i in range(n):
    k = 2 + 2

给出以下代码的大O性能。

1
2
3
4
i = n
while i > 0:
    k = 2 + 2
    i = i // 2

给出以下代码的大O性能。

1
2
3
4
for i in range(n):
    for j in range(n):
        for k in range(n):
            k = 2 + 2

给出以下代码的大O性能。

1
2
3
4
i = n
while i > 0:
    k = 2 + 2
    i = i // 2

给出以下代码的大O性能。

1
2
3
4
5
6
for i in range(n):
    k = 2 + 2
for j in range(n):
    k = 2 + 2
for k in range(n):
    k = 2 + 2

编程练习

  • 1.设计一个实验，证明列表的索引操作为常数阶。
  • 2.设计一个实验，证明字典的取值操作和赋值操作为常数阶。
  • 3.设计一个实验，针对列表和字典比较del操作的性能。
  • 4.给定一个数字列表，其中的数字随机排列，编写一个线性阶算法，找出第k小的元素，并解释为何该算法的阶是线性的。
  • 5.针对前一个练习，能将算法的时间复杂度优化到$O(n\log n)$吗？
0%