第1章 绪论

​ 本章首先讨论一些与数据结构和算法有关的基础问题，还将特别关注Python语言的一些相关情况。

1.1 计算机问题求解

​ 计算机解决问题的过程分为两个阶段：程序开发者针对要解决的问题开发出相应的程序，使用者运行程序处理问题的具体实例，完成具体计算。

1.1.1 程序开发过程

图1.1 程序开发过程

1.1.2 一个简单的例子

​ 求出任一个非负实数的平方根。使用牛顿迭代法，描述如下：

(1) 对给定的正实数x和允许误差e，令变量y取任意正实数值，如另y=x；

(2) 如果y * y与x足够接近，即|y * y - x|<e，计算结束并把y作为结果；

(3) 取z = (y + x/y)/2；

(4) 将z作为y的新值，回到步骤1。

​ 其Python程序为：

def sqrt(x):
    y = 1.0
    while abs(y * y - x) > 1e-6:
        y = (y + x/y)/2
    return y

1.2 问题求解：交叉路口的红绿灯安排

​ 只考虑红绿灯如何安排，可以保证相应的允许行驶路线互补交错，从而保证路口的交通安全。

图1.2 一个交叉路口实例的模型

​ 现在的基本想法是对行驶方向分组，使得：

(1) 同属一组的各个方向形式的车辆，均可以同时行驶，不出现相互交错的行驶路线，因此保证了安全和路线畅通。

(2) 所做的分组应该尽可能大些，以提高路口的效率（经济问题）。

1.2.1 问题分析和严格化

​ 首先罗列出路口的所有可能行驶方向，13个可行方向：AB, AC, AD, BA, BC, BD, DA, DB, DC, EA, EB, EC, ED。

图1.3 行驶路线冲突图

​ 有了冲突图，寻找安全分组的问题就可以换一种说法：为冲突图中的顶点确定一种分组，保证属于同一组的所有顶点互不邻接。

1.2.2 图的顶点分组和算法

​ 以非相邻为条件地最佳顶点分组问题，实际上对应于有名的图最佳着色问题：把顶点看作区域，把相邻看作两个区域有边界，把不同分组看作给相邻顶点以不同颜色着色。

​ 贪心法的基本想法就是根据当时掌握的信息，尽可能地向得到解的方向前进，直到不能继续再换一个方向。这样通常不能找到最优解，但是能找到“可接受的”解，即给出一种较好的分组。算法的梗概（伪代码）如下：

输入：图G                 # 记录图中的顶点连接关系
集合verts保存G中所有顶点    # 建立初始状态
设置集合groups为空集       # 记录得到的分组，元素是顶点集合
while存在未着色顶点：      # 每次迭代用贪心法找一个新分组
	选一种新颜色
    在未着色顶点中给尽量多的无互连边的点着色（构建一个分组）
    记录新着色的顶点组
# 算法结束时集合groups里记录着一种分组方式
# 算法细节还需要进一步考虑

​ 现在考虑用这个算法处理图1.3中的冲突图，假定操作按照前面列出的13个方向的顺序进行处理。操作中的情况如下：

(1) 选第1种颜色构造第1个分组：顺序选出相互不冲突的AB、AC、AD，以及与任何方向都不冲突的BA、DC和ED，做成一组；

(2) 选出BC、BD和与他们不冲突的EA作为第二组；

(3) 选出DA和DB作为第三组；

(4) 剩下的EC和EB作为第四组。

​ 在上面安排的基础上，找出verts中可用新颜色着色的顶点集的算法是：

new_group = 空集
for v in verts:
    if v与new_group中所有顶点之间都没有边:
        把verts中去掉v
        把v加入new_group
# 循环结束时new_group是可以用一种新颜色着色的顶点集合
# 用这段代替前面程序框架中主循环体里的一部分

​ 上面讨论中实际上也介绍了两种最基本的算法设计方法：

• 枚举和选择（优化）：根据问题，设法枚举出所有可能的情况，首先筛选出问题的解（为此需要判断枚举生成的结果是否为问题的解），而后从得到的解中找出最优解（这一步需要能评价解的优劣）。
• 贪心法：根据当时已知的局部信息，完成尽可能多的工作。这样做通常可以得到正确的解，但可能并非最优。对于一个复杂的问题，全面考虑的工作代价可能太高，为得到实际可用的算法，常常需要在最优方面做出妥协。

1.2.3 算法的精化和Python描述

​ Python的集合数据类型不支持元素遍历，但上述算法中需要遍历集合元素，还要在遍历中修改集合。处理这个问题的方法是在每次需要遍历时从当时的verts生成一个表，而后对表做遍历。算法中需要的图操作依赖于图的表示，需要考虑如何在Python中实现图数据结构。

• 函数vertices(G)得到G中所有顶点的集合。
• 谓词not_adjacent_with_set(v, group, G)检查顶点v与顶点集group中各顶点在图G中是否有边连接。

def coloring(G):                # 做图G的着色
    color = 0
    groups = set()
    verts = vertices(G)         # 取得G的所有顶点，依赖于图的表示
    while verts:                # 如果集合不空
        new_group = set()
        for v in list(verts):
            if not_adjacent_with_set(v, new_group, G):
                new_group.add(v)
                verts.remove(v)
        groups.add((color, new_group))
        color += 1
    return groups

​ 这个算法实际上已经是一个Python函数，能对任何一个图算出顶点分组。其中欠缺的细节就是图的表示，以及函数里涉及的两个图操作。

1.2.4 讨论

• 解唯一吗？

  解不唯一。

• 求解算法和原问题的关系

  回顾前面从问题出发最终做出一个Python程序的工作过程：

(1) 有关工作开始于交叉路口的抽象图示，首先枚举出所有允许通行方向；

(2) 根据通行方向和有关不同方向冲突的定义，画出冲突图；

(3) 把通行方向的分组问题归结为冲突图中不相邻顶点的划分问题，用求出不相邻顶点的分组作为交叉路口中可以同时通行的方向分组。

1.3 算法和算法分析

​ 本节集中讨论算法的问题，特别是算法的性质及其分析技术。

1.3.1 问题、问题实例和算法

• 问题：一个问题W是需要解决的一个具体需求。
• 问题实例：问题W的一个实例w是该问题的一个具体例子，通常可以通过一组具体的参数设定。
• 算法：解决问题W的一个算法A，是对一种计算过程的严格描述。

​ 算法的性质：有穷性，能行性，确定性，终止性，输入/输出。

​ 算法的描述：采用自然语言描述；采用在自然语言描述中结合一些数学记法或公式的描述形式；采用严格定义的形式化记法形式描述；用类似某种编程语言的形式描述算法过程，其中掺杂使用一些数学符号和记法，用于描述算法中一些细节和具体操作；采用某种伪代码形式，结合编程语言的常用结构、形式化的数学记法代表的严格描述和自然语言。

​ 算法和程序：“算法”用于指称相应计算过程的描述；而在考虑一个计算在某种语言里的具体实现和实现中的问题时，常用“程序”这一术语。

​ 算法设计与分析：所谓算法设计，就是从问题出发，通过分析和思考最终得到一个能解决问题的过程性描述的工作过程。常见的算法设计模式包括：枚举法，贪心法，分治法，回溯法（搜索法），动态规划法，分支限界法。算法分析的主要任务就是弄清算法的资源消耗。

1.3.2 算法的代价及其度量

​ 在考虑求解一个问题的具体算法时，需要考虑用它解决问题的代价，包括该算法：在求解过程中需要多少存储空间？完成问题实例的求解需要多长时间？使用者需要关心算法运行中存储占用的高位限，以及得到结果的时间。

​ 大O记法：对于单调的整数函数f，如果存在一个整数函数g和实常数c>0，使得对于充分大的n总有f(n)小于等于c·g(n)，就说函数g是f的一个渐进函数（忽略常量因子），记为f(n)=O(g(n))。易见，f(n)=O(g(n))说明在趋向无穷的极限意义下，函数f的增长速度受到函数g的约束。

​ 把上述描述方式应用于算法的代价问题。假设存在函数g，使得算法A处理规模为n的问题实例所用的时间T(n)=O(g(n))，则称O(g(n))为算法A的渐进时间复杂度，简称时间复杂度。算法的空间复杂度S(n)的定义与此类似。在算法和数据结构领域，人们常用的是下面这组渐进复杂度函数：
$O(1), O(logn), O(n), O(nlogn), O(n^2), O(n^3), O(2^n)$O(1),O(logn),O(n),O(nlogn),O(n2),O(n3),O(2n)
​ 如果有T(n)=O(g(n))，函数g(n)是算法的实际时间开销的一个上界，并不表示实际开销真正具有与g(n)同样的增长速度。

解决同一问题的不同算法

​ 考虑一个简单的问题，求斐波那契数列的第n项。使用递归算法：

def fib(n):
    if n < 2:
        return 1
    else:
        return fib(n-1) + fib(n-2)

​ 计算$F_n~$Fn​ 的时间代价，根据已有的结论；
$F_n = \lim_{n \to \infty} ( \frac {{\sqrt5}+1}{2})^n$Fn​=n→∞lim​(25​+1​)n
​ 所以计算$F_n~$Fn​ 的时间代价按n值的指数增长。

​ 求斐波那契数还有另一种简单的递推算法：

def fib(n):
    f1 = f2 = 1
    for k in range(1, n):
        f1, f2 = f2, f2 + f1
    return f2

​ 用这个算法计算$F_n~$Fn​ 的值，总的工作量与n值呈某种线性关系。

1.3.3 算法分析

​ 算法分析的目的是推导出算法的复杂度，其中最主要的技术是构造和求解递归方程。

基本循环程序

​ 这里只考虑算法的时间复杂度，考虑最基本的循环程序，其中只有顺序组合、条件分支和循环结构。分析这种算法只需要几条基本计算规则：

(1) 基本操作，认为其时间复杂度为$O(1)$O(1)。如果是函数调用，应该将其时间复杂度代入，参与整体时间复杂度的计算。

(2) 加法规则（顺序复合）。如果算法是两个部分的顺序复合，其复杂性是这两部分的复杂性之和。
$T(n)=T_1(n)+T_2(n)=O(T_1(n))+O(T_2(n))=O(max(T_1(n),T_2(n)))$T(n)=T1​(n)+T2​(n)=O(T1​(n))+O(T2​(n))=O(max(T1​(n),T2​(n)))
(3) 乘法规则（循环结构）。如果算法是一个循环，循环体将执行$T_1(n)$T1​(n)次，每次执行需要$T_2(n)$T2​(n)时间，那么：
$T(n)=T_1(n)\times T_2(n)=O(T_1(n))\times O(T_2(n))=O(T_1(n)\times T_2(n))$T(n)=T1​(n)×T2​(n)=O(T1​(n))×O(T2​(n))=O(T1​(n)×T2​(n))
(4) 取最大规则（分支结构）。如果算法是条件分支，两个分支的时间复杂性分别是$T_1(n)$T1​(n)和$T_2(n)$T2​(n)，则有：
$T(n)=O(max(T_1(n),T_2(n)))$T(n)=O(max(T1​(n),T2​(n)))
​ 现在看一个简单实例，矩阵乘法求出两个$n\times n$n×n矩阵$m_1$m1​与$m_2$m2​的乘积，存入另一个$n\times n$n×n的矩阵$m$m。

for i in range(n):
    for j in range(n):
        x = 0.0
        for k in range(n):
            x = x + m1[i][k] * m2[k][j]
        m[i][j] = x

​ 这个程序是一个两重循环，循环体是一个顺序语句，其中还有一个内嵌的循环。根据上面的复杂性计算规则：
$T(n)=O(n)\times O(n)\times (O(1)+O(n)\times O(1)+O(1))=O(n)\times O(n)\times O(n)=O(n\times n\times n)=O(n^3)$T(n)=O(n)×O(n)×(O(1)+O(n)×O(1)+O(1))=O(n)×O(n)×O(n)=O(n×n×n)=O(n3)
​ 其中$O(1)+O(n)\times O(1)+O(1)$O(1)+O(n)×O(1)+O(1)部分表示循环体的复杂度，它包含两个基本语句和一个简单循环，化简后也得$O(n)$O(n)。

递归算法的复杂度

​ 递归算法通常具有如下的算法模式：

def recur(n):
    if n == 0:
        return g(...)
    somework
    for i in range(a):
        x = recur(n/b)
        somework
    somework

​ 也就是说，$n$n值为0时直接得到结果，否则原问题将归结为$a$a个规模为$n/b$n/b的子问题，其中$a$a和$b$b是由具体问题决定的两个常量。上面描述里用somework表示，其时间复杂度可能与$n$n有关，设为$O(n^k)$O(nk)。这样得到递归方程：
$T(n)=O(n^k)+a\times T(\frac{n}{b})$T(n)=O(nk)+a×T(bn​)
​ 有如下结论：

• 如果$a>b^k$a>bk，那么$T(n)=O(n^{log_ba})$T(n)=O(nlogb​a)；

• 如果$a=b^k$a=bk，那么$T(n)=O(n^klogn)$T(n)=O(nklogn)；

• 如果$a<b^k$a<bk，那么$T(n)=O(n^k)$T(n)=O(nk)。

1.3.4 Python程序的计算代价（复杂度）

时间开销

• 基本算术运算是常量时间操作，逻辑运算是常量时间运算。

• 组合对象的操作有些是常量时间的，有些不是。

  复制和切片操作通常需要线性时间；

  list和tuple的元素访问和元素赋值，是常量时间的；

  dict操作的情况比较复杂，后面第8章有详细讨论。

• 字符串也应该看作组合对象，其许多操作不是常量时间的。

• 创建对象也需要付出空间和时间，空间和时间都与对象大小有关。通常看作线性时间和线性空间操作。

​ 在下面有关数据结构和算法的讨论中，将会介绍和分析一些Python结构和操作的效率问题。

• 构造新结构，如构造list、set等。构造新的空结构是常量时间操作，而构造一个包含$n$n个元素的结构，则至少需要$O(n)$O(n)的时间。
• 一些list操作的效率：元素访问和元素修改是常量时间操作，但一般的加入/删除元素操作都是$O(n)$O(n)时间操作。
• 字典dict操作的效率：主要操作是加入新的键-值对和基于键查找值。他们最坏情况复杂度是$O(n)$O(n)，但平均复杂度是$O(1)$O(1)。

​ 上面复杂度中的$n$n都是有关结构中的元素个数。

空间开销

​ 建立一个表或者元组，至少要占用元素个数那么多空间，如果一个表的元素个数与问题规模线性相关，建立它的空间付出至少为$O(n)$O(n)。

(1) Python的各种组合数据对象都没有预设的最大元素个数。

(2) 还应该注意Python自动存储管理系统的影响。

1.4 数据结构

​ 从程序输入和输出的角度看，用计算解决问题，可以看作实现某种信息表示形式的转换。把一种形式表示的信息送给程序，通过在计算机上运行程序，产生出另一种形式表示的信息。

1.4.1 数据结构及其分类

抽象定义与重要类别

​ 一个具体的数据结构就是一个二元组
$D=(E,R)$D=(E,R)
​ 其中的$E$E是数据结构$D$D的元素集合，是某个数据集合$\epsilon$ϵ的一个有穷子集，而$R\in E\times E$R∈E×E是$D$D的元素之间的某种关系。典型的数据结构有：

• 集合结构：其数据元素之间没有需要关注的明确关系，也就是说关系$R$R是空集。
• 序列结构：其数据元素之间有一种明确的先后关系（顺序关系）。
• 层次结构：其数据元素分属于一些不同的层次，一个上层元素可以关联着一个或者多个下层元素，关系$R$R形成一种明确的层次性，只从上层到下层。
• 树形结构：层次结构中最简单的一种关系是树形关系，其特点是在一个树形结构中只有一个最上层数据元素，称为根，其余元素都是根的直接或间接关联的下层元素。进一步说，除根元素之外的每个元素，都有且仅有一个上层元素与之关联。
• 图结构：数据元素之间可以有任意复杂的相互联系。

结构性和功能性的数据结构

• 结构性数据结构：线性结构、树结构和图结构。
• 功能性数据结构：栈、队列、优先队列、字典等。

1.4.2 计算机内存对象表示

内存单元和地址

​ 计算机中（程序中）直接使用的数据保存在计算机的内存储器（简称内存）。内存是CPU可以直接访问的数据存储设备。与之相对应的是外存储器，简称外存，如磁盘、光盘、磁带等。保存在外存里的数据必须先装入内存，而后CPU才能使用它们。

​ 内存的基本结构是线性排列的一批存储单元，每个单元的大小相同，可以保存一个单位大小的数据。具体单元大小可能因计算机的不同而有所不同。在目前最常见的计算机中，一个单元可以保存一个字节（8位二进制代码）的数据。因此存放一个整数或者浮点数，需要连续的几个单元，例如标准的浮点数需要8个单元。

​ 内存单元具有唯一编号，称为单元地址，或简称地址。单元地址从0开始连续排列，全部可用地址为从0开始的一个连续的正整数区间。

图1.4 计算机内存的基本结构

​ 在程序执行中，对内存单元的访问都通过单元的地址进行，因此，要访问一个单元，必须先掌握其地址。

对象存储和管理

​ 在Python程序运行中，建立对象时需要安排存储，还有许多与对象存储和使用有关的管理工作，解释器的一个专门子系统（称为存储管理系统）负责这些工作。另外，当一个对象不再有用时，存储管理系统也会设法回收其占用的存储，以便在将来用于存储其他对象。

对象的访问

​ 在编程语言层面，知道了一个对象的标识就可以直接访问它。已知对象标识，访问相应对象的操作可以直接映射到已知地址访问内存单元，这种操作可以在常量时间完成。

​ 如果被访问的是一个组合对象，其中包含了一组元素，这组元素被安排在一块内存区域里，而且每个元素的存储量相同。如果知道了一个组合对象的元素存储区位置，又知道要访问的元素的编号，访问元素也是$O(1)$O(1)时间操作。假设所关心的元素存储区的起始位置是内存地址$p$p，每个元素占用$a$a个内存单元，再假设元素序列中首元素的下标为0。要访问下标为$k$k的元素，通过下式能立刻计算出该元素的位置$loc(k)$loc(k)：
$loc(k)=p+k\times a$loc(k)=p+k×a
​ 上述公式是统一的，只需做一次乘法和一次加法，所用时间与元素的下标无关，与组合对象中的元素个数也无关。

​ 考虑另一种情况，假设某类组合对象都包含同样的一组元素，元素连续存放在一块存储区里，但不同元素的大小可能不同。进而，在同属这类的不同对象里，排在同样位置的元素的大小相同，进一步说，这类对象都采用同样存储方式。显然，在上面条件下，根据元素的排列顺序，可以事先算出这类对象里各元素在对象存储区中的相对位置，称为元素的存储偏移量。假设一个对象$o$o的地址为$p$p，$o$o的元素$e_i$ei​的偏移量为$r_i$ri​，立即可以算出$e_i$ei​的地址为$p+r_i$p+ri​。易见，在这种情况下，已知一个这种组合对象，访问其中元素的操作也可以在$O(1)$O(1)时间完成。

对象关联的表示

​ 在计算机内存里表示数据元素之间的联系，只有两种基本技术：

(1) 利用数据元素的存储位置隐式表示。由于内存是单元的线性序列，知道了前一个元素的位置及其大小，就能确定下一元素的位置，如果存储的是一系列大小相同的元素，就可以利用前面公式直接算出序列中任何一个元素的位置。

(2) 把数据元素之间联系也看做一种数据，显示地保存在内存中。

​ 第一种方式称为元素的顺序表示，最典型的例子之一是简单字符串。

图1.5 字符串对象的表示

​ 在上层看这是两项数据，一个整数表示字符串长度，紧接它的一块内存区域里保存字符串的内容；后一区域又是一系列单元，其中存储着字符串的各个字符。知道了整个存储块的开始位置，只需常量时间就能找到字符串里的任何一个字符。

​ 第二种技术称为对象的链接表示技术，假设现在记录书籍的信息包括作者和书名，一种合理的方式是采用三个独立部分的组合表示一个完整的书籍对象。首先是一个二元结构，它表示书籍对象的整体，另外两个独立的字符串分别表示书籍对象的两个成分。在二元结构里记录两个成分字符串的引用信息。这样，掌握了这个二元结构，通过其中记录的数据关联就可以找到有关书籍的所有信息了。

图1.6 一种书籍对象的表示

​ 连续结构和链接结构是所有数据结构构造的基础。

1.4.3 Python对象和数据结构

Python变量和对象

​ 在Python程序里，可以通过初始化给变量约束一个值，还可以通过赋值修改变量的值。这里的值就是对象，给变量约束一个对象，就是把该对象的标识（内存位置）存入该变量。Python变量的值都是对象，可以是基本整数、浮点数等类型的对象，也可以是组合类型的对象，如list等。

Python对象的表示

​ 一个复杂对象内部可能包含几个子部分，相互之间通过链接建立联系。

Python的几个标准数据类型

• list（表）对象可以包含任意多个任意类型的元素，元素访问和修改都是常量时间操作。
• tuple（元组）的对象是不可变对象。
• dict（字典）的键必须是不变对象（元组、字符串等）。