数据结构与算法分析基本术语 2021.3.21
- 1、基本术语
- 2、数据
-
- 2.1 数据的逻辑结构
- 2.2 数据的存储结构
-
- 2.2.1 顺序存储
- 2.2.2 链接存储
- 2.2.3 索引存储
- 2.2.4 散列存储
- 3、算法分析
-
- 3.1 算法分析举例
1、基本术语
虽然计算机具有非常广泛的应用领域，可以用于科学计算、情报检索、企业管理等，但它的核心功能概括起来却只有一个：处理数据。但计算机处理的数据绝不是杂乱无章的，而是有着某种内在联系的，只有分清楚数据的内在联系并合理地组织数据，才能对它们进行有效的管理和存储。
2、数据
计算机科学中，数据的含义极其广泛：一切能够输入到计算机中并被计算机成U型处理的信息，包括文字、表格、图像等，都成为数据。
结点（数据元素）是组成数据的基本单位，在计算机程序中通常把结点作为一个整体进行考虑和处理。
一般情况下，一个结点中含有若干个字段（数据项），字段是构成数据的最小单位。
结点与结点之间的逻辑关系成为数据的逻辑结构。
数据在计算机中的存储表示成为数据的存储结构，如磁盘上的文件、内存中的数组等。
数据结构并没有公认的标准定义，但把某种逻辑关系组织起来的一组结点，按一定的存储方式存储于计算机中，并在其上定义了一个运算的集合，称为一个数据结构。
数据类型作为高级程序设计语言中的一个基本概念，与数据结构的概念密切相关。一方面，在程序设计语言中，每一个数据都属于某种数据类型。类型明显或隐含地规定了数据的取值范围、存储方式以及允许进行的运算，因此数据类型是在程序设计语言中已经实现了的数据结构。另一方面，在程序设计过程中，当需要引入某种新的数据结构时，必须借助编程语言所提供的数据类型来描述数据的存储结构。
2.1 数据的逻辑结构
在大多数情况下，数据的逻辑结构可以用二元组 S = ( D , R ) S=(D,R) S=(D,R)来表示。其中，D是结点的有限集合；R是结点有序对的集合，表示D上的一种关系。例如，二元组list=(D,R1),tree=(D,R2)和graph=(D,R3)分别描述了具有5个结点的三种不同的逻辑结构，其中
D = { a , b , c , d , e } D=\{a,b,c,d,e\} D={a,b,c,d,e} R 1 = { < a , b > , < b , c > , < c , d > , < d , e > } R_{1}=\{<a,b>,<b,c>,<c,d>,<d,e>\} R1={<a,b>,<b,c>,<c,d>,<d,e>} R 2 = { < a , b > , < a , c > , < b , d > , < b , e > } R_{2}=\{<a,b>,<a,c>,<b,d>,<b,e>\} R2={<a,b>,<a,c>,<b,d>,<b,e>} R 3 = { < a , b > , < a , c > , < d , a > , < e , c > } R_{3}=\{<a,b>,<a,c>,<d,a>,<e,c>\} R3={<a,b>,<a,c>,<d,a>,<e,c>}
对于任意一个逻辑结构 S = ( D , R ) S=(D,R) S=(D,R)，若 a ∈ D ， b ∈ D a\in D，b \in D a∈D，b∈D， < a , b > ∈ R <a,b> \in R <a,b>∈R，则称a是b的前驱，b是a的后继；若某结点没有前驱，则称该结点为开始结点；若某结点没有后继，则称该结点为终端节点。例如，在list结构中，a是开始结点，e是终端节点；在tree结构中，a是开始结点，c、d、e是终端节结点；在graph结构中，d和e是开始结点，b和c是终端结点。
数据的逻辑结构可分为线性结构和非线性结构两大类。在线性结构中，开始结点和终端结点都是唯一的，除了开始结点和终端结点以外，其余结点都有且仅有一个前驱，有且仅有一个后继。非线性结构又可以细分为树形结构和图状结构两类。在树形结构中，每个结点最多只有一个前驱，但可以有多个后继，可以有多个终端结点。在图状结构中，每个结点的前驱和后继的数目都可以是任意的，因此可能没有开始结点和终端节点，也可能有多个开始结点、多个终端结点。在上述的三个实例中，list属于线性结构，tree属于树形结构，graph属于图状结构。
除二元组外，数据的逻辑结构还有其他表示方法。例如，对于非线性结构，通常采用图示法；用小圆圈表示结点，在圈内或圈外附近标注结点名称或数值，用带箭头的弧线表示结点之间的关系。下图所示的是上例的逻辑结构tree和graph。
对于线性结构，可以用一个带括号的结点序列表示之。例如，list结构可简单地表示为（a,b,c,d,e）。在实际应用中，数据的逻辑结构可能会非常复杂，为了有效地对数据进行处理，必须首先搞清楚数据的逻辑结构，对数据进行合理的组织。
2.2 数据的存储结构
数据在计算机中的存储既要求存储各结点的数值，又需要存储结点与结点间的逻辑关系。在实际的应用当中，可根据问题规模（通常是指结点数目的多少）和运算种类等因素适当选择，这里将介绍四种基本的存储结构：顺序存储、链接存储、索引存储和散列存储。
2.2.1 顺序存储
顺序存储是把逻辑上相邻的结点存储在一组连续的存储单元中，其结点之间的逻辑关系由存储单元地址间的关系隐含表示。假定每个结点占用一个存储单元，数据从200号单元开始由低地址向高地址方向存放，则线性结构实例lis D = { a , b , c , d , e } D=\{a,b,c,d,e\} D={a,b,c,d,e}t的顺序存储结构如下图所示：
| 200 | 201 | 202 | 203 | 204 |
|---|---|---|---|---|
| a | b | c | d | e |
顺序存储结构
顺序存储的主要优点是节省存储空间，因为分配给数据的存储单元全用于存放结点的数值，结点之间的逻辑关系没有占用额外的存储空间。用这种方法来存储线性结构的结点时，可实现对各结点的随机访问。这是因为线性结构中每个结点都对应一个序号（开始结点的序号为1，它的后继结点的序号为2，…），可以根据结点的序号i，计算出结点的存储地址
L o c ( i ) = q + ( i − 1 ) × p Loc(i) = q + ( i - 1) \times p Loc(i)=q+(i−1)×p
其中，p是每个结点所占单元数；q是第一个节点所占单元的首地址。
顺序存储的主要缺点是不便于修改，在对结点进行插入、删除运算时，可能要移动一系列的结点。例如，要删除list结构中的第3个结点c，使list结构由(a,b,c,d,e)变成(a,b,d,e)。删除操作则必须将结点d和e往左移动一个单元，操作结果如下图(a)所示；或者将结点a和b往右移动一个单元，操作结果如下图(b)所示。移动结点的目的是要保证在进行了删除操作后，剩余结点仍然占用一片连续的存储单元。
| 200 | 201 | 202 | 203 | 204 |
|---|---|---|---|---|
| a | b | d | e |
（a）后面的结点往前移
| 200 | 201 | 202 | 203 | 204 |
|---|---|---|---|---|
| a | b | d | e |
（b）前面的结点往后移
2.2.2 链接存储
链接存储是给每个结点附加指针字段，用于存放相邻结点的存储地址。假定给实例list中的每个结点附加一个“后继指针”字段，用于存放后继结点的首地址，则可得到如图（a）所示的list链接存储表示。图中，每个结点占用两个连续的存储单元，一个存放结点的数值，另一个存放后继结点的首地址。
链接存储的主要优点是便于修改，在进行插入、删除运算时，仅需要修改结点的指针字段值，不必移动结点。例如，在图(a)所示的链接存储结构上，若要实现删除操作，使list结构由（a,b,c,d,e）变成(a,b,d,e)，则只要将207号单元的内容由202改为208即可。操作结果如图(b)所示。若要实现插入操作，使list结构由(a,b,c,d,e)变成(a,x,b,c,d,e)，则首先在存储器中找到两个连续的空单元，假设这两个空单元的地址是100号和101号，然后将x存入新结点的数值字段（100号单元）中，将结点b的存储单元首地址206存入新结点的指针字段（101号单元）中，最后将新结点的存储单元首地址100存入结点a的指针字段（201号单元）中，操作结果如图（c）所示。
与顺序存储方法相比，链接存储的主要缺点是存储空间的利用率较低，因为分配给数据的存储单元有一部分被用来存放结点之间的逻辑关系了。另外，由于逻辑上相邻的节点在存储器中不一定相邻，因此，在用这种方法存储的线性结构上不能对结点进行随机访问。
2.2.3 索引存储
索引存储是根据结点的序号确定结点的存储地址，具体做法是：建立索引表和节点表；将各结点的数值按任意顺序存放在节点表中，而将每个结点的存储地址（即在节点表中的位置）用顺序存储方法存入索引表中。对于线性结构来说，各结点的存储地址在索引表中是按结点的序号依次排列的。图（a）是list的一种索引存储表示。
线性结构采用索引存储后，可以对结点进行随机访问。在进行插入、删除运算时，由于只需移动存储在索引表中的结点的存储地址，而不必移动存储在结点表中的结点的数值，所以仍可保持较高的运算效率（这是因为，在一般情况下，结点中总包含有多个字段，移动一个节点的数值要比移动一个结点的地址花费更多的时间）。
如果要在上图所示的索引存储结构上实现删除操作，使list结构由(a,b,c,d,e)变成(a,b,d,e)，则只需将结点c的存储地址202从索引表中删除即可，操作结果如图（b）所示。
2.2.4 散列存储
散列存储是根据结点的值确定结点的存储地址，具体做法是：以结点中某个字段的值为自变量，通过某个函数（称为散列函数）计算出对应的函数值，再把i当作结点的存储地址。假定list结构中5个节点的数值是下列5个字符串：‘Wuhan’、‘Nanjing’、‘Shanghai’、‘Xian’、‘Beijing’。选用函数
L o c ( k e y ) = a s c ( l e f t ( k e y , 1 ) ) m o d 8 Loc(key)=asc(left(key,1)) mod 8 Loc(key)=asc(left(key,1))mod8来计算结点的存储地址，其中，asc(left(key,1))表示取字符串key中第一个字符的ASCII码，mod是取模运算，计算结果如下：
| key | Wuhan | Nanjing | Shanghai | Xian | Beijing |
|---|---|---|---|---|---|
| asc(key) | 87 | 78 | 83 | 88 | 66 |
| Loc(key) | 7 | 6 | 3 | 2 |
于是，可以得到下图所示list的散列存储表示。
| Xian | Beijing | Shanghai | Nanjing | Wuhan |
|---|
0 1 2 3 4 5 6 7
散列存储结构 散列存储的优点是查找速度快，只要给出待查找结点的数值，就有可能立即算出结点的存储地址。 与前三种存储方法不同的是，散列存储方法只存储结点的数值，不存储结点与结点之间的逻辑关系。散列存储方法一般只用于要求对数据能够进行快速查找、插入的场合。 采用散列存储的关键是要选择一个好的散列函数和处理“冲突”的办法。 在用高级语言编程时，可以用编程语言所提供的数据类型来描述数据的存储结构。例如，用“一维数组”表示一组连续的存储单元，来实现顺序存储结构、索引存储结构和散列存储结构；用C++语言中的“指针”来实现链接存储结构。 ## 2.3 数据的运算 数据的运算是数据结构的一个重要研究内容，它和数据的逻辑结构、存储结构有着密切的联系。数据的各种运算都是在逻辑结构上定义的，但具体的实现要在一定的存储结构上进行。在不同的应用场合，会对数据有各种各样的运算要求，常见的运算包括：**查找**、**插入**、**删除**和**排序**。数据运算用**算法**来表示，算法是一个和**程序**非常相似的概念，二者的主要区别在于：==程序一定要用程序设计语言书写==，而==算法则不必（例如，算法可以是一个流程图）==。 - 1）查找 * 在数据结构中查找数值字段等于给定值的结点。 - 2）插入 * 在数据结构中适当位置插入一个新结点。 - 3）删除 * 从数据结构中删除某个结点。 - 4）排序 * 重新排列线性结构中各结点的逻辑顺序。
3、算法分析
对于数据的任何一种运算，如果数据的存储结构不同，则其算法描述一般是不相同的，即使在存储结构相同的情况下，由于可以采用不同的求解策略，往往也可以有许多不同的算法，一般来说，好的算法应具有如下四个特征：
- (1) 正确：算法必须满足问题的要求，对合法的输入能产生问题要求的输出结果；对非法的输入能作出适当的反应或处理。
- (2) 可读：算法是给人看的，其可读性有助于人们对算法的理解，一个晦涩难懂的算法易于隐藏错误，而且难以调试和修改。
- (3) 运行时间较短。
-
(4) 占用较少的存储空间。
在这里，算法分析不是分析算法是否正确或是否容易阅读，而是分析算法执行过程中所需的时间和存储空间。算法的执行时间和所需的存储空间主要与问题规模有关。问题规模是一个和输入有关的量，例如向量的长度、矩阵的阶数等，可以说算法的执行时间和所需的存储空间都是问题规模的函数，进行算法分析就是要找出这种函数关系。由于在大多数情况下，算法在执行过程中所需的最大存储空间是容易估算的，所以算法分析主要是分析算法执行时间与问题规模之间的关系。
算法的执行时间等于算法中各语句执行时间的总和，而某个语句的执行时间等于该语句执行一次所需时间与执行次数的乘积。然而，在大多数情况下，精确统计算法中每个语句的执行次数和执行一次所需的时间都是非常困难的，为了分析的方便，算法的执行时间通常表示成数量级的形式：
T ( n ) = O ( f ( n ) ) T(n)=O(f(n)) T(n)=O(f(n))
其含义为：当问题规模n足够大时，算法的执行时间T(n)和函数f(n)成正比。或者说，存在正常数c和n0，当n≥n0时，|T(n)|≤c|f(n)|。如果算法的执行时间T(n)与问题规模无关，是个常数，则记作T(n)=O(1)。在进行算法分析时，经常会用到如下三个定理：
定理一：若 T ( n ) = a m n m + a m − 1 n m − 1 + . . . + a 1 n + a 0 T(n)=a_{m}n^{m}+a_{m-1}n^{m-1}+...+a_{1}n+a_{0} T(n)=amnm+am−1nm−1+...+a1n+a0是一个m次多项式，则 T ( n ) = O ( n m ) T(n)=O(n^{m}) T(n)=O(nm)。
证明 取 n 0 = 1 ， 当 n ≥ n 0 时 n_{0}=1，当n≥n_{0}时 n0=1，当n≥n0时，有
∣ T ( n ) ∣ ≤ ∣ a m ∣ n m + ∣ a m − 1 ∣ n m − 1 + . . . + ∣ a 1 ∣ n + ∣ a 0 ∣ ≤ ( ∣ a m ∣ + ∣ a m − 1 ∣ + . . . + ∣ a 1 ∣ + ∣ a 0 ∣ ) n m |T(n)|≤|a_{m}|n^{m}+|a_{m-1}|n^{m-1}+...+|a_{1}|n+|a_{0}|≤(|a_{m}|+|a_{m-1}|+...+|a_{1}|+|a_{0}|)n^{m} ∣T(n)∣≤∣am∣nm+∣am−1∣nm−1+...+∣a1∣n+∣a0∣≤(∣am∣+∣am−1∣+...+∣a1∣+∣a0∣)nm
取 c = ∣ a m ∣ + ∣ a m − 1 ∣ + . . . + ∣ a 1 ∣ + ∣ a 0 ∣ c=|a_{m}|+|a_{m-1}|+...+|a_{1}|+|a_{0}| c=∣am∣+∣am−1∣+...+∣a1∣+∣a0∣，定理得证。
定理二：若 T 1 ( n ) 、 T 2 ( n ) T_{1}(n)、T_{2}(n) T1(n)、T2(n)分别是算法P1、P2的执行时间，并且
T 1 ( n ) = O ( f ( n ) ) T_{1}(n)=O(f(n)) T1(n)=O(f(n)) T 2 ( n ) = O ( g ( n ) ) T_{2}(n)=O(g(n)) T2(n)=O(g(n))
则依次执行算法P1和P2，总的执行时间
T ( n ) = O ( m a x ( ∣ f ( n ) ∣ , ∣ g ( n ) ∣ ) T(n)=O(max (|f(n)|,|g(n)|) T(n)=O(max(∣f(n)∣,∣g(n)∣)
证明 根据假设可知，存在正常数 c 1 c_{1} c1、 c 2 c_{2} c2、 n 1 n_{1} n1和 n 2 n_{2} n2，当n≥ n 1 n_{1} n1时，有 ∣ T 1 ( n ) ∣ ≤ c 1 ∣ f ( n ) ∣ |T_{1}(n)|≤c_{1}|f(n)| ∣T1(n)∣≤c1∣f(n)∣；当n≥ n 2 n_{2} n2时，有 ∣ T 2 ( n ) ∣ ≤ c 2 ∣ g ( n ) ∣ |T_{2}(n)|≤c_{2}|g(n)| ∣T2(n)∣≤c2∣g(n)∣。若依次执行算法算法P1和P2，则总的执行时间
∣ T ( n ) ∣ ≤ ∣ T 1 ( n ) ∣ + ∣ T 2 ( n ) ∣ ≤ c 1 ∣ f ( n ) ∣ + c 2 ∣ g ( n ) ∣ ≤ 2 m a x ( c 1 , c 2 ) m a x ( ∣ f ( n ) ∣ , ∣ g ( n ) ∣ ) |T(n)|≤|T_{1}(n)|+|T_{2}(n)|≤c_{1}|f(n)|+c_{2}|g(n)|≤2max(c_{1},c_{2})max (|f(n)|,|g(n)|) ∣T(n)∣≤∣T1(n)∣+∣T2(n)∣≤c1∣f(n)∣+c2∣g(n)∣≤2max(c1,c2)max(∣f(n)∣,∣g(n)∣)
取 c = 2 m a x ( c 1 , c 2 ) , n 0 = m a x ( n 1 , n 2 ) , c=2max(c_{1},c_{2}),n_{0}=max(n_{1},n_{2}), c=2max(c1,c2),n0=max(n1,n2),定理得证。
定理三：若 T 1 ( n ) 、 T 2 ( n ) T_{1}(n)、T_{2}(n) T1(n)、T2(n)分别是算法P1、P2的执行时间，并且
T 1 ( n ) = O ( f ( n ) ) T_{1}(n)=O(f(n)) T1(n)=O(f(n)) T 2 ( n ) = k ( n ) T 1 ( n ) T_{2}(n)=k(n)T_{1}(n) T2(n)=k(n)T1(n)则 T 2 ( n ) = O ( k ( n ) f ( n ) ) T_{2}(n)=O(k(n)f(n)) T2(n)=O(k(n)f(n))
证明 ∣ T 2 ( n ) ∣ = ∣ k ( n ) ∣ ∣ T 1 ( n ) ∣ ≤ ∣ k ( n ) ∣ ∣ c 1 ∣ ∣ f ( n ) ∣ = c 1 ∣ k ( n ) f ( n ) ∣ |T_{2}(n)|=|k(n)||T_{1}(n)|≤|k(n)||c_{1}||f(n)|=c_{1}|k(n)f(n)| ∣T2(n)∣=∣k(n)∣∣T1(n)∣≤∣k(n)∣∣c1∣∣f(n)∣=c1∣k(n)f(n)∣
取 c = c 1 , c=c_{1}, c=c1,定理得证。
用数量级形式 O ( f ( n ) O(f(n) O(f(n)表示算法执行时间 T ( n ) T(n) T(n)的时候，函数 f ( n ) f(n) f(n)通常取较简单的形式，如1、log2n、n、nlog2n、n2、n3、2n等。在n较大的情况下，常见的时间复杂度之间存在如下关系：
O ( 1 ) < O ( l o g 2 n ) < O ( n ) < O ( n l o g 2 n ) < O ( n 2 ) < O ( n 3 ) < O ( 2 n ) O(1)<O(log_{2}n)<O(n)<O(nlog_{2}n)<O(n^{2})<O(n^{3})<O(2^{n}) O(1)<O(log2n)<O(n)<O(nlog2n)<O(n2)<O(n3)<O(2n)
3.1 算法分析举例
例1 假设A[1]~A[n]中存放了n个整数，下面程序段的功能是确定其中值最大的整数在数组中的下标i。请分析程序段中每个语句的执行次数，并用数量级形式表示这个程序段的执行时间。
i=1; for(j=2;j<=n;j++) if(A[j]>A[i]) i=j;
解：第1行的赋值语句执行1次；第2行的for语句执行n次；第3行的if语句执行n-1次；第4行的赋值语句最多执行n-1次。由于程序段中语句总的执行次数是2n~3n-1次，因此，这个程序执行时间是O(n)。
例2 假设A[1]~A[n]中存放了n个整数，其中n>100。下面程序段的功能是求其中前100个整数的平均值。请分析程序段中每个语句的执行次数，并用数量级形式表示这个程序段的执行时间。
s=0.0; for(i=1;i<=100;i++) s=s+A[i]; cout<< s/100;
解：这个程序段共有4行，每一行语句分别执行了1次、101次、100次和1次。由于程序段中语句的执行次数和n无关，因此，这个程序段的执行时间是O(1)。
例3 下面程序段的功能是从n阶整型矩阵中找出两个值最小的整数，请分析其时间复杂度。
m1=32767; m2=m1; for(i=0; i< n; i++) for(j=0; j< n; j++) if(A[i] [j]< m1) {m2=m1;m1=A[i] [j];} else if(A[i] [j]< m2) m2=A[i] [j];
解：执行第1行赋值语句所需时间是O(1)，执行一遍内循环体所需时间也是O(1)，由于内循环体总工执行了n2次，因此，程序段的执行时间为O(n2)。
例4 下面的程序段可用于求xn，请分析其时间复杂度。
y=1;u=x;v=n; while(v>0) { if(v%2 == 1) y=y*u; u=u*v;v=v/2; } cout<< y;
解：这个程序段的执行时间主要用在while循环上，循环次数和v的大小有关。由于v的初始值是n，每循环一遍，v的值被减半，因此，循环次数不超过 ⌊ l o g 2 n ⌋ \lfloor log_{2}n\rfloor ⌊log2n⌋ +1次（符号 ⌊ ⌋ \lfloor \rfloor ⌊⌋表示向下取整）。执行一遍循环体所需时间与n无关，是O(1)。因此，程序段的执行时间为
T ( n ) = ( ⌊ l o g 2 n ⌋ + 1 ) O ( 1 ) = O ( l o g 2 n ) T(n)=(\lfloor log_{2}n \rfloor +1)O(1)=O( log_{2}n) T(n)=(⌊log2n⌋+1)O(1)=O(log2n)
例5 下面的算法是用来求解著名的汉诺塔问题的，请分析算法的时间复杂度。
void hanoi(int n,char a,char b,char c) { if(n>0) { hanoi(n-1,a,c,b); cout<< a<<"->" << c; hanoi(n-1,b,a,c); } }
解：这是一个递归算法，器其执行时间T(n)与参数n有关。当n=0时，只执行返回操作，所需时间为T(n)=O(1)；当n>0时，执行了一个输出语句，所需时间为O(1)，执行了两个递归调用语句，所需时间为2T(n-1)。因此，算法的执行时间是
T ( n ) T(n) T(n) = 2 T ( n − 1 ) + 2 0 O ( 1 ) =2T(n-1)+2^{0}O(1) =2T(n−1)+20O(1)
= 2 2 T ( n − 2 ) + ( 2 1 + 2 0 ) O ( 1 ) =2^{2}T(n-2)+(2^{1}+2^{0})O(1) =22T(n−2)+(21+20)O(1)
= 2 3 T ( n − 3 ) + ( 2 2 + 2 1 + 2 0 ) O ( 1 ) =2^{3}T(n-3)+(2^{2}+2^{1}+2^{0})O(1) =23T(n−3)+(22+21+20)O(1)
. . . ... ...
= 2 n T ( 0 ) + ( 2 n − 1 + 2 n − 2 + . . . + 2 0 ) O ( 1 ) =2^{n}T(0)+(2^{n-1}+2^{n-2}+...+ 2^{0})O(1) =2nT(0)+(2n−1+2n−2+...+20)O(1)
= ( 2 n + 2 n − 1 + 2 n − 2 + . . . + 2 0 ) O ( 1 ) =(2^{n}+2^{n-1}+2^{n-2}+...+ 2^{0})O(1) =(2n+2n−1+2n−2+...+20)O(1)
= ( 2 n + 1 − 1 ) O ( 1 ) =(2^{n+1}-1)O(1) =(2n+1−1)O(1)
= O ( 2 n ) =O(2^{n}) =O(2n)