第1章概述 f if(n<=1) retum(1); retum(n·fact(n-1);② 解:设fact(n)的运行时间函数是Tan)。该函数中语句①的运行时间是O(1),语句②的运 行时间是Tn-1)+O(1),其中O(1)为常量运行时间。 由此可得 fact(n)的时间复杂度为On) (6)当算法运行次数无法确定时,程序的运行时间的分析。 在上面的几种情况下,算法的运行次数是可以确定的,但在某种情形下算法的运行次数 可能是无法确定的,如在一组记录中查找某个关键字。查找过程是从第一个记录开始,有可 能一次就查找成功,也有可能最后一次才查找成功,还有可能根本查找不到。此时如何求它 的时间复杂度呢? 如果不能查找成功,它的运算次数是n(n是被查找的记录个数),时间复杂度是O(n) 如能够查找成功,对于这一类算法就要求它的平均运算次数,用平均运算次数表示整个算法 的运算次数。 平均值=总的运算次数/被运算的记录数 在查找和排序算法中,都可用此方法。 例16分析下列算法的时间复杂度(假设查找成功) void search( struct element[ ], int n, struct keytype k) i int i; rn+1].key=k i=0; while (r[i]. keyl=k if (i<n+1) printf(("%adn",可 else printf ("No key! ") 解:这是一个顺序查找关键字的算法程序。其运行次数不可知,所以求其平均运行次数。 在查找的过程中,比较一次可找到在第一个位置的关键字,比较两次可找到在第二个位置的 关键字,……,比较n次可找到在第n个位置的关键字。因此总的比较次数为1+2+3+… +(n-1)+n=n(n+1)2。所以 平均运算次数=总的比较次数被比较的关键字个数= n(n+1)/2n+1 n 2 即算法的平均运算时间为fn)= n 2。所求算法的时间复杂度为m)=On),即 Tn=O(n)
数据结构 在算法时间复杂度的分析中,Tm)的数量级通常有以下几种。 常数:O(1)。 线性函数:O(n) 幂函数:O(n)、On3) 对数函数:O(log2n)、O(n*logn)。 指数函数:O(2) 当n的值较大时,各种不同数量级之间存在着如下关系: 0(1)<O(log2n)<On)<O+ogn)<On2)<O(n)<O2) 算法时间复杂度的数量级越大,表示该算法的效率越低,反之越高。 1.52算法的空间复杂度分析 空间复杂度是对一个算法在运行过程中临时占用存储空间大小的量度。算法在计算机存 储器内占用的存储空间主要分为三部分:算法源代码本身占用的存储空间;算法输入输出数 据所占用的存储空间;算法运行过程中临时占用的存储空间。考虑一个算法的空间复杂度时, 要综合分析这三个方面的因素,通常记作:Sn)=O(n)。其中n为问题的规模(或大小), 对于它的衡量,也采用类似时间复杂度的形式来表示。 在对一个算法进行时间复杂度和空间复杂度的分析时,二者往往不能兼顾。考虑好的时 间复杂度,就得牺牲空间复杂度的性能。考虑好的空间复杂度,就得牺牲时间复杂度的性能。 因此二者要从算法使用的频率、处理的数据规模等多方面综合协调 习题 、单项选择题 1.数据结构是指()。 A.数据元素的组织形式 B.数据类型 C.数据存储结构 D.数据定义 数据在计算机存储器内表示时,物理地址与逻辑地址不相同的,称之为()。 A.存储结构 B.逻辑结构 C.链式存储结构 D.顺序存储结构 3.树形结构是数据元素之间存在一种()。 A.一对一关系 B.多对多关系 C.多对一关系 D.一对多关系 4.设语句x++的时间是单位时间,则以下语句的时间复杂度为()。 for(i=1; i<=n; i++) for(i=i; j<=n; j++) X++ A.O(1) B. O(n C. O(n) D. O(n) 5.算法分析的目的是(1),算法分析的两个主要方面是(2) (1)A.找出数据结构的合理性 B.研究算法中的输入和输出关系 2
第1章概述 C.分析算法的效率以求改进D.分析算法的易懂性和文档性 (2)A.空间复杂度和时间复杂度B.正确性和简明性 C.可读性和文档性 D.数据复杂性和程序复杂性 6.计算机算法指的是(1),它具备输入,输出和(2)等5个特性。 (1)A.计算方法 B.排序方法 C.解决问题的有限运算序列D.调度方法 (2)A.可行性,可移植性和可扩充性B.可行性,确定性和有夯性 C.确定性,有穷性和稳定性D.易读性,稳定性和安全性 7.数据在计算机内有链式和顺序两种存储方式,在存储空间使用的灵活性上,链式存储 比顺序存储要()。 A.低 B.高 C.相同 D.不好说 8.数据结构作为一门独立的课程出现是在()年。 A.1946 B.1953 C.1964 D.1968 9.数据结构只是研究数据的逻辑结构和物理结构,这种观点() A.正确 B.错误 C.前半句对,后半句错 D.前半句错,后半句对 10.计算机内部数据处理的基本单位是()。 A.数据B.数据元素C.数据项 D.数据库 二、填空题 1.数据结构按逻辑结构可分为两大类,分别是 和 2.数据的逻辑结构有4种基本形态,分别是 和 3.线性结构反映结点间的逻辑关系是的,非线性结构反映结点间的逻辑关系是 的 4.一个算法的效率可分为 效率和 效率。 5.在树形结构中,树根结点没有 结点,其余每个结点的有且只有 个前 趋驱结点;叶子结点没有 结点;其余每个结点的后续结点可以 6,在图形结构中,每个结点的前趋结点数和后续结点数可以 ∴.缦性结构中元素之间存在关系;树形结构中元素之间存在关系;图 形结构中元素之间存在关系。 8.下面程序段的时间复杂度是 In i=0; i<n; i++) =0<j++) 9.下面程段的时间复杂度是 while(s<n i++;
数据结构 10.下面程序段的时间复杂度是 s=0; for(i=0; i <n; i++) forG=0j<n;j++) s+=B[]t]; sumS, 1.下面程序段的时间复杂度是 while(i<=n) =i3; 12.衡量算法正确性的标准通常是 13.算法时间复杂度的分析通常有两种方法,即 和 的方法,通常我们 对算法求时间复杂度时,采用后一种方法。 求下列程序段的时间复杂度 for(i-I; i<n; i++) forf=i计+lj=nj++) 2 =0 for(i=l; i<n; i ++) for(=lj≤=n-ij+) 3. int ij, k for(i=0; i<n; i++) for(=0;j<=n; j++) c[il[j}=0; for(k=0; k<n; k++) c[i[i=a[lk]°blk[i in-I while((i>=O)&&Adj!=k)) return(): 5. fact(n) if(n<=D) return(D); return(n"fact(n-1);
2亘 胜表 本章将讨论最常用而且最简单的一种数据结构——线性表。线性表的逻辑结构属于线性 结构,存储结构主要有两种:顺序存储结构和链式存储结构。我们把顺序存储的线性表称为 顺序表,把链式存储的线性表称为链表 21基本概念和运算 211线性表的定义 线性表是n个数据元素的有限序列,其中n(n≥0)为线性表的长度。 例2126个英文字母的字母表(A,B,…,Zz)是一个线性表,表中数据元素是单 个字母,线性表的长度是26。表中A"是第一个数据元素,Z是最后一个数据元素,A称为B 的直接前趋,B称为A的直接后继。 例22某班学生的单科成绩(89,67,95,…,88)是一个线性表。此时线性表中数据元 素是一个整数(成绩)。 在稍复杂的线性表中,一个数据元素可以由若干数据项组成,此时常将数据元素称为记 录,含有大量记录的线性表又称文件。如上例中的数据元素可改 为由学号、姓名、成绩三个数据项组成,如图2.1所示。 学号姓名|成绩 综合上述三个例子可见,线性表中的数据元素可以各种各 张平 样,但同一线性表中的所有元素的性质是相同的,即属于同数2 王伟 据对象,相邻数据元素之间存在着序偶关系。一般将n=0的线性 表称为空表,n>0的线性表记为(a,a2,…,a,…,an),其中a1 李丽 是第一个元素,又称起始结点;an是最后一个元素,又称终端结 点。a是第i个元素,i为数据元素a在线性表中的位序。a属于50范军 某一数据对象的数据元素,它可以是一个数,一个符号,一条记图21学生单科成绩表 录,甚至是更加复杂的信息。除第一个元素a1和最后一个元素an外,表中每一元素a(2≤ ≤n-1)有且仅有一个直接前趋a1,有且仅有一个直接后继a1 212线性表的运算 在线性表上常用的运算有如下8种。 (1)取元素:求线性表中指定数据元素的位序