计算机学院信息教研室
lixuejun@swust.edu.cn
D
S 第二章 面向对象程序设计和算法性能分析
2.1 <数据结构 >的主要内容及教学要求
2.2 基本术语
2.3 算法描述及分析计算机学院信息教研室
lixuejun@swust.edu.cn
D
S
2.1 <数据结构 >的主要内容
200080-3 班号
2419237 计算机学院办公室电话号码
621002 西南科技大学邮编
510102780618748 身份证号码例 1：
200080-32419237621002510102780618748
结论 1,杂乱的数据不能表达和交流信息计算机学院信息教研室
lixuejun@swust.edu.cn
D
S 2.1 <数据结构 >的主要内容例 2,电话号码簿 (a1,b1) (a2,b2)…(a n,bn)
其中,ai为某人姓名,bi为该人的电话号码。
要求：设计一个算法，给定一个姓名时，
能查出此人的电话号码。
如果姓名和电话号码的排列次序无规律，
则只能逐一比较姓名进行查找
如果姓名按字典顺序组织，则查找就快捷多了结论 2,数据之间是有联系的这些联系常常影响算法的选择和效率。
,DS,就是要研究数据之间的联系。
计算机学院信息教研室
lixuejun@swust.edu.cn
D
S 2.1 <数据结构 >的主要内容例 3：大学学生管理机构学校一系,．．八系,．．
一年级 二年级 三年级 四年级
１班,．．８班张三．．．李四结论３,数据之间是有结构的例３中数据之间呈分层结构（树状结构）
,DS,就是要研究 数据之间的各类结构 。
计算机学院信息教研室
lixuejun@swust.edu.cn
D
S 2.1 <数据结构 >的主要内容例４：图书目录管理设每个书目含：书名，作者，登录号，分类，出版年月对图书目录常有如下操作：
查找：某书在书库中是否存在？
插入：购进新书时的登录；
删除：报废或丢失的书，需从目录中去掉；
结论４,在某种数据结构上可定义一组运算
,DS,就是要研究各类数据结构上的各种运算。
计算机学院信息教研室
lixuejun@swust.edu.cn
D
S 2.1 <数据结构 >的主要内容综上所述：,DS,主要研究内容：
数据的各种逻辑结构和物理结构，以及它们之间的相应关系；
对每种结构定义相适应的各种运算；
设计出相应的算法；
分析算法的效率。
常见的数据结构有：线性表、栈、队列、
数组、串、树、图等。
计算机学院信息教研室
lixuejun@swust.edu.cn
D
S 2.1 <数据结构 >的教学要求
学会分析计算机加工的数据对象的特性，
以便选择适当的数据结构和存储结构以及相应的算法，并初步掌握算法的时间分析和空间分析的技巧。
进行复杂程序设计的训练过程，要求所写的程序结构正确，正确易读计算机学院信息教研室
lixuejun@swust.edu.cn
D
S 数据结构与问题求解
1,在计算机中建立一个与实际问题有比较密切对应关系的 模型 ；
2,计算机内部的 数据 表示了需要被处理的实际对象，包括其内在的性质和关系；
3,处理这些数据的 程序 则模拟对象领域中的实际过程；
4,将计算机程序的运行 结果 在实际领域中给予解释，便得到实际问题的解。
计算机学院信息教研室
lixuejun@swust.edu.cn
D
S 2.2 基本术语
数据 （ Data),所有能被 计算机处理 的 符号 的集合。
数据元素 （ Data Element）,是数据这个集合中的一个个体。
设给定数据集合为：
D={d1,d2，．．．,dn}
则 di属于 D,并称 di为 数据元素。
数据项 （ Data Item）,数据元素常常还可分为若干个数据项，数据项是数据具有意义的最小单位。
计算机学院信息教研室
lixuejun@swust.edu.cn
D
S 2.2 基本术语
数据类型,在一种程序设计语言中，变量所具有的数据种类。
例 1,在 FORTRAN语言中，变量的数据类型有整型、实型、和复数型
例 2、在 C语言中，变量的数据类型：基本类型和构造类型基本类型：整型、浮点型、字符型构造类型：数组、结构、联合、指针、枚举型、自定义计算机学院信息教研室
lixuejun@swust.edu.cn
D
S 2.2 基本术语数据对象 （ Data Object）,具有相同特性的数据元素的集合。
例如：数据集合 D={0,1,…,A,B,…,Z}
则,数据对象正整数 N＝｛ 0,1,… ｝
数据对象字母 C＝｛ A,B,…,Z ｝
数据元素是数据的一个个体，
数据对象是数据的一个子集。
计算机学院信息教研室
lixuejun@swust.edu.cn
D
S 2.2 基本术语
数据结构 （ Data Structure）,是带有结构的数据元素的集合。
所谓 结构 就是数据元素之间的关系，即描述数据元素之间的运算及运算规则。
用集合的形式描述，数据结构是一个二元组：
DS=(D,R)
其中,D是数据元素的集合,R是 D上 关系的集合。
简言之，数据元素和其相互关系称为数据结构计算机学院信息教研室
lixuejun@swust.edu.cn
D
S
2.2 基本术语例 复数的数据结构定义如下：
Complex=(C,R)
其中,C是含两个实数的集合 ﹛ C1,C2﹜,
分别表示复数的实部和虚部。
R={P},P是定义在集合上的一种关系
{〈 C1,C2〉 }。
计算机学院信息教研室
lixuejun@swust.edu.cn
D
S
数据结构主要指 逻辑结构 和 物理结构
2.2 基本术语
逻辑结构 （ Logical Structure）：
指数据元素之间的结构关系。
存储 结构 （ Store Structure）：
指数据结构在机内的表示，也称为物理结构。
计算机学院信息教研室
lixuejun@swust.edu.cn
D
S 2.2 基本术语数据之间的相互关系称为 逻辑结构 。通常分为四类基本结构：
一,集合 结构中的数据元素除了同属于一种类型外，别无其它关系。
二,线性结构 结构中的数据元素之间存在一对一的关系。
三,树型结构 结构中的数据元素之间存在一对多的关系。
四,图状结构或网状结构 结构中的数据元素之间存在多对多的关系。
计算机学院信息教研室
lixuejun@swust.edu.cn
D
S 2.2 基本术语
数据结构在计算机中有 两种 不同的表示方法：
顺序表示和非顺序表示由此得出两种不同的存储结构,顺序存储结构 和 链式存储结构
顺序存储结构,用数据元素在存储器中的相对位置来表示数据元素之间的逻辑关系。
链式存储结构,在每一个数据元素中增加一个存放地址的指针（ ），用此指针来表示数据元素之间的逻辑关系。
存储结构 指数据结构在计算机机内的表示。
计算机学院信息教研室
lixuejun@swust.edu.cn
D
S
数据对象可以是有限的，也可以是无限的。
数据结构不同于数据类型，也不同于数据对象，它不仅要描述数据类型的数据对象，而且要描述数据对象各元素之间的相互关系。
抽象数据类型 (ADT),一个数学模型以及定义在该模型 上的一组操作。
抽象数据类型实际上就是对该数据结构的定义。
因为它定义了一个数据的逻辑结构以及在此结构上的一组算法。
用三元组描述为：（Ｄ，Ｓ，Ｐ）
D为数据对象,S是 D上的关系集,P为对 D的基本操作集
2.2 基本术语计算机学院信息教研室
lixuejun@swust.edu.cn
D
S 2.3 算法 描述和算法分析一,算法 （ Algorithm）
１,算法概念：算法是一个有限的指令集，
遵循指令流可以完成特定的功能。
２、算法基本特性：
有穷性,算法经有限步后结束；
确定性,每一条指令的含义明确，无二义性；
可执行性,每一步是可执行的（有限的时间内完成；
输入,一个算法有零个或多个输入，这些输入取自于某个特定的对象集合。
输出,一个算法有一个或多个输出，这些输出是同输入有着某些特定关系的量。
计算机学院信息教研室
lixuejun@swust.edu.cn
D
S 2.3 算法 描述和算法分析
3,算法设计的要求评价一个好的算法有以下几个标准,(4)
正确性 (Correctness ) 算法应满足具体问题的需求。
可读性 (Readability) 算法应该好读。以有利于阅读者对程序的理解。
健 壮 性 (Robustness) 算法应具有容错处理。
当输入非法数据时，算法应对其作出反应，而不是产年莫名其妙的输出结果。
计算机学院信息教研室
lixuejun@swust.edu.cn
D
S 2.3 算法 描述和算法分析
4、算法与程序的区别
算法 是解决问题的一种方法或一个过程，考虑如何将输入转换成输出，一个问题可以有多种算法。
程序 是用某种程序设计语言对算法的具体实现。
主要区别在,有穷性 和 描述方法
程序可以是无穷的，例如 OS,算法是有穷的；
程序是用程序设计语言描述，在机器上可以执行；
算法还可以用框图、自然语言等方式描述。
效率与存储量需求 效率指的是算法执行的时间；存储量需求指算法执行过程中所需要的最大存储空间。一般，这两者与问题的规模有关。
计算机学院信息教研室
lixuejun@swust.edu.cn
D
S 2.3 算法描述和 算法分析二．算法分析如何衡量一个 正确算法 的好坏？
衡量的三个尺度：
运行所花费的时间（算法的时间特性）；
所占用存储空间的大小（算法的空间特性）；
其他（可读性、易调性、健壮性等）。
时间和空间特性的巨大改进源于更好的数据结构或算法。
计算机学院信息教研室
lixuejun@swust.edu.cn
D
S 2.3 算法描述和 算法分析
算法效率的度量对一个算法要作出全面的分析可分成两个阶段进行，即 事先分析 和 事后测试
事先分析 求出该算法的一个时间界限函数
事后测试 收集此算法的执行时间和实际占用空间的统计资料。
定义,如果存在两个正常数 c和 n0,对于所有的 n≧ n0,有︱ f(n) ︳ ≦ c｜ g(n) ︳
则记作 f(n)=O(g(n))
计算机学院信息教研室
lixuejun@swust.edu.cn
D
S 2.3 算法描述和 算法分析
语句频度 （ Frequency Count）：
语句可能重复执行的最大次数。
时间复杂度 （ Time Complexity）：
设算法中所有语句的语句频度为 t(n)，
f(n)是当 n趋向无穷大时与 t(n)为同阶无穷大，
则算法的时间复杂度 T(n)=O(f(n))
其中,n为算法计算量或称为规模（ size）；
f(n)是运算时间随 n增大时 的增长率；
O(f(n))是 算法时间特性的量度。
计算机学院信息教研室
lixuejun@swust.edu.cn
D
S 2.3 算法描述和 算法分析例 2-1,for(I=1； I<=n;++I)
for(j=1;j<=n;++j)
{
c[I][j]=0;
for(k=1;k<=n;++k)
c[I][j]+=a[I][k]*b[k][j];
}
由于是一个三重循环，每个循环从 1到 n,则总次数为,n× n× n=n3
时间复杂度为 T(n)=O(n3)
计算机学院信息教研室
lixuejun@swust.edu.cn
D
S 2.3 算法描述和 算法分析
例 2-2,for(I=1;I<=n;I = 2* I)
printf(“I = %d/n”,I )
设语句频度为 f(n)
2 f(n)<=n,
即 f(n)<= log2n
其时间复杂度为,O(log2n)
计算机学院信息教研室
lixuejun@swust.edu.cn
D
S 2.3 算法描述和 算法分析? 例 3,for(I=1;I<=n;++I)
for(j=1;j<=n;++j)
{
++x;
s+=x;
}
语句频度为,2n2
其时间复杂度为,O(n2) 即时间复杂度为平方阶。
计算机学院信息教研室
lixuejun@swust.edu.cn
D
S 2.3 算法描述和 算法分析
定理：若 A(n)=a m n m +a m-1 n m-1
+…+a 1n+a0是一个 m次多项式，则
A(n)=O(n m)
证略。
例 4,for(i=2;i<=n;++I)
for(j=2;j<=i-1;++j)
{
++x;
a[I][j]=x;
}
计算机学院信息教研室
lixuejun@swust.edu.cn
D
S 语句频度为：
1+2+3+…+ n-2
=(1+n-2) × (n-2)/2
=(n-1)(n-2)/2
=n2-3n+2
∴ 时间复杂度为 O(n2)
即此算法的时间复杂度为平方阶,
一个算法时间为 O(1)的算法，它的基本运算执行的次数是固定的。因此，总的时间由一个常数（即零次多项式）来限界。而一个时间为 O(n2)的算法则由一个二次多项式来限界。
2.3 算法描述和 算法分析计算机学院信息教研室
lixuejun@swust.edu.cn
D
S 以下六种计算算法时间的多项式是最常用的。
其关系为：
O(1)<O(log2n)<O(n)<O(n log2n)
<O(n2)<O(n3)
指数时间的关系为：
O(2n)<O(n!)<O(nn)
当 n取得很大时，指数时间算法和多项式时间算法在所需时间上非常悬殊。因此，
只要有人能将现有指数时间算法中的任何一个算法化简为多项式时间算法，那就取得了一个伟大的成就。
2.3 算法描述和 算法分析计算机学院信息教研室
lixuejun@swust.edu.cn
D
S 有的情况下，算法中基本操作重复执行的次数还随问题的输入数据集不同而不同。 例如：Void BubbleSort(Datatype a[],int n)
{ int i,j,flag = 1;
Datatype temp;
for(i = 1; i < n && flag == 1;i++) //flag判断本次排序过程是否有交换动作
{ flag = 0;
for(j = 0;j < n-i;j++){
if(a[j].key > a[j+1].key){
flag = 1;temp = a[j];
a[j] = a[j+1];a[j+1] = temp;
}}
}}
最好情况,0次
2.3 算法描述和 算法分析计算机学院信息教研室
lixuejun@swust.edu.cn
D
S 第二章 小结
2.1 <数据结构 >的主要内容及教学要求
2.2 基本术语
2.3 算法描述及分析
lixuejun@swust.edu.cn
D
S 第二章 面向对象程序设计和算法性能分析
2.1 <数据结构 >的主要内容及教学要求
2.2 基本术语
2.3 算法描述及分析计算机学院信息教研室
lixuejun@swust.edu.cn
D
S
2.1 <数据结构 >的主要内容
200080-3 班号
2419237 计算机学院办公室电话号码
621002 西南科技大学邮编
510102780618748 身份证号码例 1：
200080-32419237621002510102780618748
结论 1,杂乱的数据不能表达和交流信息计算机学院信息教研室
lixuejun@swust.edu.cn
D
S 2.1 <数据结构 >的主要内容例 2,电话号码簿 (a1,b1) (a2,b2)…(a n,bn)
其中,ai为某人姓名,bi为该人的电话号码。
要求：设计一个算法，给定一个姓名时，
能查出此人的电话号码。
如果姓名和电话号码的排列次序无规律，
则只能逐一比较姓名进行查找
如果姓名按字典顺序组织，则查找就快捷多了结论 2,数据之间是有联系的这些联系常常影响算法的选择和效率。
,DS,就是要研究数据之间的联系。
计算机学院信息教研室
lixuejun@swust.edu.cn
D
S 2.1 <数据结构 >的主要内容例 3：大学学生管理机构学校一系,．．八系,．．
一年级 二年级 三年级 四年级
１班,．．８班张三．．．李四结论３,数据之间是有结构的例３中数据之间呈分层结构（树状结构）
,DS,就是要研究 数据之间的各类结构 。
计算机学院信息教研室
lixuejun@swust.edu.cn
D
S 2.1 <数据结构 >的主要内容例４：图书目录管理设每个书目含：书名，作者，登录号，分类，出版年月对图书目录常有如下操作：
查找：某书在书库中是否存在？
插入：购进新书时的登录；
删除：报废或丢失的书，需从目录中去掉；
结论４,在某种数据结构上可定义一组运算
,DS,就是要研究各类数据结构上的各种运算。
计算机学院信息教研室
lixuejun@swust.edu.cn
D
S 2.1 <数据结构 >的主要内容综上所述：,DS,主要研究内容：
数据的各种逻辑结构和物理结构，以及它们之间的相应关系；
对每种结构定义相适应的各种运算；
设计出相应的算法；
分析算法的效率。
常见的数据结构有：线性表、栈、队列、
数组、串、树、图等。
计算机学院信息教研室
lixuejun@swust.edu.cn
D
S 2.1 <数据结构 >的教学要求
学会分析计算机加工的数据对象的特性，
以便选择适当的数据结构和存储结构以及相应的算法，并初步掌握算法的时间分析和空间分析的技巧。
进行复杂程序设计的训练过程，要求所写的程序结构正确，正确易读计算机学院信息教研室
lixuejun@swust.edu.cn
D
S 数据结构与问题求解
1,在计算机中建立一个与实际问题有比较密切对应关系的 模型 ；
2,计算机内部的 数据 表示了需要被处理的实际对象，包括其内在的性质和关系；
3,处理这些数据的 程序 则模拟对象领域中的实际过程；
4,将计算机程序的运行 结果 在实际领域中给予解释，便得到实际问题的解。
计算机学院信息教研室
lixuejun@swust.edu.cn
D
S 2.2 基本术语
数据 （ Data),所有能被 计算机处理 的 符号 的集合。
数据元素 （ Data Element）,是数据这个集合中的一个个体。
设给定数据集合为：
D={d1,d2，．．．,dn}
则 di属于 D,并称 di为 数据元素。
数据项 （ Data Item）,数据元素常常还可分为若干个数据项，数据项是数据具有意义的最小单位。
计算机学院信息教研室
lixuejun@swust.edu.cn
D
S 2.2 基本术语
数据类型,在一种程序设计语言中，变量所具有的数据种类。
例 1,在 FORTRAN语言中，变量的数据类型有整型、实型、和复数型
例 2、在 C语言中，变量的数据类型：基本类型和构造类型基本类型：整型、浮点型、字符型构造类型：数组、结构、联合、指针、枚举型、自定义计算机学院信息教研室
lixuejun@swust.edu.cn
D
S 2.2 基本术语数据对象 （ Data Object）,具有相同特性的数据元素的集合。
例如：数据集合 D={0,1,…,A,B,…,Z}
则,数据对象正整数 N＝｛ 0,1,… ｝
数据对象字母 C＝｛ A,B,…,Z ｝
数据元素是数据的一个个体，
数据对象是数据的一个子集。
计算机学院信息教研室
lixuejun@swust.edu.cn
D
S 2.2 基本术语
数据结构 （ Data Structure）,是带有结构的数据元素的集合。
所谓 结构 就是数据元素之间的关系，即描述数据元素之间的运算及运算规则。
用集合的形式描述，数据结构是一个二元组：
DS=(D,R)
其中,D是数据元素的集合,R是 D上 关系的集合。
简言之，数据元素和其相互关系称为数据结构计算机学院信息教研室
lixuejun@swust.edu.cn
D
S
2.2 基本术语例 复数的数据结构定义如下：
Complex=(C,R)
其中,C是含两个实数的集合 ﹛ C1,C2﹜,
分别表示复数的实部和虚部。
R={P},P是定义在集合上的一种关系
{〈 C1,C2〉 }。
计算机学院信息教研室
lixuejun@swust.edu.cn
D
S
数据结构主要指 逻辑结构 和 物理结构
2.2 基本术语
逻辑结构 （ Logical Structure）：
指数据元素之间的结构关系。
存储 结构 （ Store Structure）：
指数据结构在机内的表示，也称为物理结构。
计算机学院信息教研室
lixuejun@swust.edu.cn
D
S 2.2 基本术语数据之间的相互关系称为 逻辑结构 。通常分为四类基本结构：
一,集合 结构中的数据元素除了同属于一种类型外，别无其它关系。
二,线性结构 结构中的数据元素之间存在一对一的关系。
三,树型结构 结构中的数据元素之间存在一对多的关系。
四,图状结构或网状结构 结构中的数据元素之间存在多对多的关系。
计算机学院信息教研室
lixuejun@swust.edu.cn
D
S 2.2 基本术语
数据结构在计算机中有 两种 不同的表示方法：
顺序表示和非顺序表示由此得出两种不同的存储结构,顺序存储结构 和 链式存储结构
顺序存储结构,用数据元素在存储器中的相对位置来表示数据元素之间的逻辑关系。
链式存储结构,在每一个数据元素中增加一个存放地址的指针（ ），用此指针来表示数据元素之间的逻辑关系。
存储结构 指数据结构在计算机机内的表示。
计算机学院信息教研室
lixuejun@swust.edu.cn
D
S
数据对象可以是有限的，也可以是无限的。
数据结构不同于数据类型，也不同于数据对象，它不仅要描述数据类型的数据对象，而且要描述数据对象各元素之间的相互关系。
抽象数据类型 (ADT),一个数学模型以及定义在该模型 上的一组操作。
抽象数据类型实际上就是对该数据结构的定义。
因为它定义了一个数据的逻辑结构以及在此结构上的一组算法。
用三元组描述为：（Ｄ，Ｓ，Ｐ）
D为数据对象,S是 D上的关系集,P为对 D的基本操作集
2.2 基本术语计算机学院信息教研室
lixuejun@swust.edu.cn
D
S 2.3 算法 描述和算法分析一,算法 （ Algorithm）
１,算法概念：算法是一个有限的指令集，
遵循指令流可以完成特定的功能。
２、算法基本特性：
有穷性,算法经有限步后结束；
确定性,每一条指令的含义明确，无二义性；
可执行性,每一步是可执行的（有限的时间内完成；
输入,一个算法有零个或多个输入，这些输入取自于某个特定的对象集合。
输出,一个算法有一个或多个输出，这些输出是同输入有着某些特定关系的量。
计算机学院信息教研室
lixuejun@swust.edu.cn
D
S 2.3 算法 描述和算法分析
3,算法设计的要求评价一个好的算法有以下几个标准,(4)
正确性 (Correctness ) 算法应满足具体问题的需求。
可读性 (Readability) 算法应该好读。以有利于阅读者对程序的理解。
健 壮 性 (Robustness) 算法应具有容错处理。
当输入非法数据时，算法应对其作出反应，而不是产年莫名其妙的输出结果。
计算机学院信息教研室
lixuejun@swust.edu.cn
D
S 2.3 算法 描述和算法分析
4、算法与程序的区别
算法 是解决问题的一种方法或一个过程，考虑如何将输入转换成输出，一个问题可以有多种算法。
程序 是用某种程序设计语言对算法的具体实现。
主要区别在,有穷性 和 描述方法
程序可以是无穷的，例如 OS,算法是有穷的；
程序是用程序设计语言描述，在机器上可以执行；
算法还可以用框图、自然语言等方式描述。
效率与存储量需求 效率指的是算法执行的时间；存储量需求指算法执行过程中所需要的最大存储空间。一般，这两者与问题的规模有关。
计算机学院信息教研室
lixuejun@swust.edu.cn
D
S 2.3 算法描述和 算法分析二．算法分析如何衡量一个 正确算法 的好坏？
衡量的三个尺度：
运行所花费的时间（算法的时间特性）；
所占用存储空间的大小（算法的空间特性）；
其他（可读性、易调性、健壮性等）。
时间和空间特性的巨大改进源于更好的数据结构或算法。
计算机学院信息教研室
lixuejun@swust.edu.cn
D
S 2.3 算法描述和 算法分析
算法效率的度量对一个算法要作出全面的分析可分成两个阶段进行，即 事先分析 和 事后测试
事先分析 求出该算法的一个时间界限函数
事后测试 收集此算法的执行时间和实际占用空间的统计资料。
定义,如果存在两个正常数 c和 n0,对于所有的 n≧ n0,有︱ f(n) ︳ ≦ c｜ g(n) ︳
则记作 f(n)=O(g(n))
计算机学院信息教研室
lixuejun@swust.edu.cn
D
S 2.3 算法描述和 算法分析
语句频度 （ Frequency Count）：
语句可能重复执行的最大次数。
时间复杂度 （ Time Complexity）：
设算法中所有语句的语句频度为 t(n)，
f(n)是当 n趋向无穷大时与 t(n)为同阶无穷大，
则算法的时间复杂度 T(n)=O(f(n))
其中,n为算法计算量或称为规模（ size）；
f(n)是运算时间随 n增大时 的增长率；
O(f(n))是 算法时间特性的量度。
计算机学院信息教研室
lixuejun@swust.edu.cn
D
S 2.3 算法描述和 算法分析例 2-1,for(I=1； I<=n;++I)
for(j=1;j<=n;++j)
{
c[I][j]=0;
for(k=1;k<=n;++k)
c[I][j]+=a[I][k]*b[k][j];
}
由于是一个三重循环，每个循环从 1到 n,则总次数为,n× n× n=n3
时间复杂度为 T(n)=O(n3)
计算机学院信息教研室
lixuejun@swust.edu.cn
D
S 2.3 算法描述和 算法分析
例 2-2,for(I=1;I<=n;I = 2* I)
printf(“I = %d/n”,I )
设语句频度为 f(n)
2 f(n)<=n,
即 f(n)<= log2n
其时间复杂度为,O(log2n)
计算机学院信息教研室
lixuejun@swust.edu.cn
D
S 2.3 算法描述和 算法分析? 例 3,for(I=1;I<=n;++I)
for(j=1;j<=n;++j)
{
++x;
s+=x;
}
语句频度为,2n2
其时间复杂度为,O(n2) 即时间复杂度为平方阶。
计算机学院信息教研室
lixuejun@swust.edu.cn
D
S 2.3 算法描述和 算法分析
定理：若 A(n)=a m n m +a m-1 n m-1
+…+a 1n+a0是一个 m次多项式，则
A(n)=O(n m)
证略。
例 4,for(i=2;i<=n;++I)
for(j=2;j<=i-1;++j)
{
++x;
a[I][j]=x;
}
计算机学院信息教研室
lixuejun@swust.edu.cn
D
S 语句频度为：
1+2+3+…+ n-2
=(1+n-2) × (n-2)/2
=(n-1)(n-2)/2
=n2-3n+2
∴ 时间复杂度为 O(n2)
即此算法的时间复杂度为平方阶,
一个算法时间为 O(1)的算法，它的基本运算执行的次数是固定的。因此，总的时间由一个常数（即零次多项式）来限界。而一个时间为 O(n2)的算法则由一个二次多项式来限界。
2.3 算法描述和 算法分析计算机学院信息教研室
lixuejun@swust.edu.cn
D
S 以下六种计算算法时间的多项式是最常用的。
其关系为：
O(1)<O(log2n)<O(n)<O(n log2n)
<O(n2)<O(n3)
指数时间的关系为：
O(2n)<O(n!)<O(nn)
当 n取得很大时，指数时间算法和多项式时间算法在所需时间上非常悬殊。因此，
只要有人能将现有指数时间算法中的任何一个算法化简为多项式时间算法，那就取得了一个伟大的成就。
2.3 算法描述和 算法分析计算机学院信息教研室
lixuejun@swust.edu.cn
D
S 有的情况下，算法中基本操作重复执行的次数还随问题的输入数据集不同而不同。 例如：Void BubbleSort(Datatype a[],int n)
{ int i,j,flag = 1;
Datatype temp;
for(i = 1; i < n && flag == 1;i++) //flag判断本次排序过程是否有交换动作
{ flag = 0;
for(j = 0;j < n-i;j++){
if(a[j].key > a[j+1].key){
flag = 1;temp = a[j];
a[j] = a[j+1];a[j+1] = temp;
}}
}}
最好情况,0次
2.3 算法描述和 算法分析计算机学院信息教研室
lixuejun@swust.edu.cn
D
S 第二章 小结
2.1 <数据结构 >的主要内容及教学要求
2.2 基本术语
2.3 算法描述及分析
