? 什么是数据结构
? 抽象数据类型
? 算法定义
? 性能分析与度量
“学生”表格
学 号 姓 名 性别 籍 贯 出生年月
1 98 131 刘激扬 男 北 京 19 79.12
2 98 164 衣春生 男 青 岛 19 79.07
3 98 165 卢声凯 男 天 津 19 81.02
4 98 182 袁秋慧 女 广 州 19 80.10
5 98 224 洪 伟 男 太 原 19 81.01
6 98 236 熊南燕 女 苏 州 19 80.03
7 98 297 宫 力 男 北 京 19 81.01
8 98 310 蔡晓莉 女 昆 明 19 81.02
9 98 318 陈 健 男 杭 州 19 79.12
“课程”表格
课程编号 课 程 名 学时
024002 程序设计基础 64
024010 汇编语言 48
024016 计算机原理 64
024020 数据结构 64
024021 微机技术 64
024024 操作系统 48
024026 数据库原理 48
“选课单” 包含如下信息
学号 课程编号 成绩 时间
学生选课系统中实体构成的网状关系
学生
(学号,姓名,性别,籍贯 )
课程
(课程号,课程名,学分 )
选课
(学号,课程号,成绩 )
UNIX文件系统的系统结构图
/ (root)
bin lib user etc
math ds sw yin tao xie
Stack.cppQueue.cpp Tree.cpp
数据 （ data）
? 数据是信息的载体，是描述客观事物
的数、字符、以及所有能输入到计算
机中，被计算机程序识别和处理的符
号的集合。
? 数值性数据
? 非数值性数据
数据元素 (data element)
? 数据的 基本单位 。在计算机程序中常
作为一个整体进行考虑和处理。
? 有时一个数据元素可以由若干 数据项
(Data Item)组成。 数据项 是 具有独立
含义的最小标识单位 。
? 数据元素又称为元素、结点、记录。
数据对象 (data object)
? 数据对象是具有相同性质的数据元素
的集合。
?整数数据对象
N = { 0,?1,?2,… }
?学生数据对象
什么是数据结构
定义,
指某一数据对象的所有数据成员
之间的关系。记为：
Data_Structure = {D,R}
其中,D 是某一数据对象,R 是该
对象中所有数据成员之间的关系的有
限集合。
N 个网点之间的连通关系
树形关系 网状关系
1
5
2
4
36
1
5
2
4
36
数据结构 是数据的 组织形式
? 数据元素间的 逻辑关系,即数据的
逻辑结构 ；
? 数据元素及其关系在计算机存储内
的表示，即数据的 存储表示 ；
? 数据的运算，即对数据元素施加的
操作 。
数据的逻辑结构
? 数据的逻辑结构 从逻辑关系上描述
数据, 与数据的存储无关 ；
? 数据的逻辑结构可以看作是 从具体
问题抽象出来的数据模型 ；
? 数据的逻辑结构 与数据元素本身的
形式、内容无关 ；
? 数据的逻辑结构与数据元素的相对
位置无关。
数据的逻辑结构分类
? 线性结构
? 线性表
? 非线性结构
? 树
? 图（或网络）
线性结构
树形结构
树 二叉树 二叉搜索树
14131211
2 3 4
5 6 7 8 9 10 3
1 5
8
7
10
11
9
987
4 5 6
62 3 13
1
bin dev etc lib user
1
堆结构
,最大”堆, 最小”堆
12
3 5 4 8
7
11
10
2
9
16
4
10
1211
5
1
2
36
98
7
图结构 网络结构
1 2
5
6
4
3
1 2
5 4
3611
33
18
14
6
6
5
16
19
21
数据的存储结构
? 数据的存储结构是逻辑结构用计算
机语言的实现；
? 数据的存储结构依赖于计算机语言。
? 顺序存储表示
? 链接存储表示
? 索引存储表示
? 散列存储表示
抽象数据类型
? 数据类型
定义,一组性质相同的值的集合,以
及定义于这个值集合上的一组操作
的总称,
? C语言中的基本数据类型
char int float double void
字符型 整型 浮点型 双精度型 无值
? 构造数据类型由 基本数据类型 或 构
造数据类型 组成。
? 构造数据类型由 不同成分类型 构成。
? 基本数据类型可以看作是 计算机中
已实现的数据结构 。
? 数据类型就是数据结构，不过它是从编
程者的角度来使用的。
? 数据类型是模板，必须定义属于某种数
据类型的变量，才能参加运算。
抽象数据类型
(ADTs,Abstract Data Types)
?由用户定义，用以表示应用问题的
数据模型
?由 基本的数据类型 组成,并包括 一组
相关的服务 （或称操作）
?信息隐蔽 和 数据封装,使用与实现
相分离
抽
象
数
据
类
型
查找 登录 删除 修改
符 号 表
自然数的抽象数据类型定义
ADT NaturalNumber is
objects,一个整数的有序子集合,它开始于 0,
结束于机器能表示的最大整数 (MaxInt)。
Function,对于所有的 x,y ? NaturalNumber;
False,True ? Boolean,+,-,<,==,=等
都是可用的服务。
Zero( ), NaturalNumber 返回自然数 0
IsZero(x), if (x==0) 返回 True
Boolean else 返回 False
Add (x,y), if (x+y<=MaxInt)返回 x+y
NaturalNumber else 返回 MaxInt
Subtract (x,y), if (x < y) 返回 0
NaturalNumber else 返回 x - y
Equal (x,y), if (x==y) 返回 True
Boolean else 返回 False
Successor (x), if (x==MaxInt) 返回 x
NaturalNumber else 返回 x+1
end NaturalNumber
算法定义
? 定义,一个有穷的指令集,这些指令为
解决某一特定任务规定了一个运算序列
? 特性：
? 输入 有 0个或多个输入
? 输出 有一个或多个输出 (处理结果 )
? 确定性 每步定义都是确切、无歧义的
? 有穷性 算法应在执行有穷步后结束
? 有效性 每一条运算应足够基本
? 事例学习,选择排序问题
? 明确问题,递增排序
? 解决方案,逐个选择最小数据
? 算法框架：
for ( int i = 0; i < n-1; i++ ) { //n-1趟
从 a[i]检查到 a[n-1];
若最小整数在 a[k],交换 a[i]与 a[k];
}
? 细化程序,程序 SelectSort
算法设计 自顶向下，逐步求精
void selectSort ( int a[ ],int n ) {
//对 n个整数 a[0],a[1],…,a[n -1]按递增顺序排序
for ( int i = 0; i < n-1; i++ ) {
int k = i;
//从 a[i]查到 a[n-1],找最小整数,在 a[k]
for ( int j = i+1; j < n; j++ )
if ( a[j] < a[k] ) k = j;
int temp = a[i]; a[i] = a[k]; a[k] = temp;
}
}
性能分析与度量
? 算法的性能标准
? 算法的后期测试
? 算法的事前估计
算法的性能标准
? 正确性
? 可使用性
? 可读性
? 效率
? 健壮性
算法的后期测试
在算法中的某些部位插装时间函数
time ( )
测定算法完成某一功能所花费时间
顺序搜索 (Sequenial Search)
int seqsearch ( int a[ ],int n,int x ) {
//在 a[0],…,a[n -1]中搜索 x
int i = 0;
while ( i < n && a[i] != x )
i++;
if ( i == n ) return -1;
return i;
}
插装 time( ) 的计时程序
double start,stop;
time (&start);
int k = seqsearch (a,n,x);
time (&stop);
double runTime = stop - start;
printf (,%d%d\n ",n,runTime );
算法的事前估计
? 空间复杂度
? 时间复杂度
空间复杂度度量
? 存储空间的固定部分
程序指令代码的空间，常数、简单变量、
定长成分 (如数组元素、结构成分、对象
的数据成员等 )变量所占空间
? 可变部分
尺寸与实例特性有关的成分变量所占空
间、引用变量所占空间、递归栈所用空
间、通过 new和 delete命令动态使用空间
时间复杂度度量
? 运行时间 = 算法中每条语句执行时间之和。
? 每条语句执行时间 = 该语句的执行次数
（频度） * 语句执行一次所需时间。
? 语句执行一次所需时间取决于 机器的指令
性能和速度 和 编译所产生的代码质量,很
难确定。
? 设每条语句执行一次所需时间为单位时间，
则一个算法的运行时间就是该算法中所有
语句的频度之和。
例 求两个 n阶方阵的乘积 C = A?B
void MatrixMultiply ( int A[n][n],int B[n][n],
int C[n][n] ) {
for ( int i = 0; i < n; i++ ) … n+1
for ( int j = 0; j < n; j++ ) { … n(n+1)
C[i][j] = 0; … n2
for ( int k = 0; k < n; k++ ) … n2(n+1)
C[i][j] = C[i][j] + A[i][k] * B[k][j];
… n3
}
} 2n
3 + 2n2 + 2n +1
时间复杂度
? 算法中所有语句的频度之和是 矩阵阶数 n
的函数
T(n) = 2n3 + 2n2 + 2n +1
? 一般地，称 n 是问题的规模。则时间复
杂度 T(n) 是问题规模 n 的函数。
? 当 n趋于无穷大时，把时间复杂度的数量
级（阶）称为算法的渐进时间复杂度
T(n) = O(n3)
渐进时间复杂度
? 大 O表示法
? 加法规则 针对并列程序段
T(n,m) = T1 (n) + T2 (m)
= O(max (f (n),g (m)))
c < log2n < n < nlog2n < n2 < n3 <
2n < 3n < n!
变量计数
x = 0; y = 0;
for ( int k = 0; k < n; k ++ )
x ++;
for ( int i = 0; i < n; i++ )
for ( int j = 0; j < n; j++ )
y ++;
T1(n) = O(1)
T2(n) = O(n)
T3(n) = O(n2)
T(n) = T1(n)+T2(n)+T3(n) = O( max( 1,n,n2 ) )
= O(n2)
? 乘法规则 针对嵌套程序段
T (n,m) = T1 (n) * T2 (m)
= O(f (n)*g (m))
//起泡排序
void bubbleSort ( int A[n] ) {
//对表逐趟比较,n是表当前长度
int i = 1; exchange = 1;
while ( i < n && exchange ) {
BubbleExchange ( A,i,exchange );
i++;
} //一趟比较
}
void BubbleExchange( int A[n],int i ){
for ( int j = n -1; j >= i; j--)
if ( A[j-1] > A[j] ) {
int temp = A[j-1];
A[j-1] = A[j];
A[j] = temp;; //发生逆序,交换
}
}
渐进时间复杂度
O(f (n)*g (n)) = O(n2)
?
?
?
???1
1 2
1n
i
)n ( ni)(n?
BubbleSort n-1趟 T1(n) = O(n)
BubbleExchange ( )
n-i 次比较
? 有时,算法的时间复杂度不仅依赖于问题
规模 n，还与输入实例的初始排列有关。
? 在数组 A[n] 中查找给定值 k 的算法：
int i = n-1;
while ( i >= 0 && A[i] != k )
i--;
return i;
? 算法的语句 i-- 的频度不仅与 n 有关，
还与 A[ ] 中各元素的取值,以及 k 的取
值 有关。
? 例：设有两个算法在同一机器上运行，
其执行时间分别为 100n2和 2n，问：要
使前者快于后者,n至少要取多大？
解答：
问题是找出满足 100n2 <= 2n 的最小的
n。用试探法：
n = 13时,100n2 = 16900 > 2n = 8192
n = 14时,100n2 = 19600 > 2n = 16384
n = 15时,100n2 = 22500 < 2n = 32764
取 n = 15 满足要求。
填空例题
( ① )由某一数据对象和该对象
中各个数据成员间的关系组成。依据所
有数据成员之间关系的不同,( ① )
分为两大类,( ② )和 ( ③ )。
在 ( ② )中的各个数据成员依次
排列在一个线性序列中； ( ③ )的各
个数据成员不再保持在一个线性序列中，
每个数据成员可能与零个或多个其他数
据成员发生联系。
根据视点的不同，数据结构分为数
据的 ( ④ )和 ( ⑤ )。 ( ④ )是
面向问题的,( ⑤ )是面向计算机的。
判断下列叙述的对错 。 如果正确, 在题前
打, ?”, 否则打, ?” 。
(1) 数据元素是数据的最小单位 。
(2) 数据结构是数据对象与对象中数据元
素之间关系的集合 。
(3) 数据结构是具有结构的数据对象 。
(4) 数据的逻辑结构是指各数据元素之间
的逻辑关系, 是用户按使用需要建立的 。
(5) 算法和程序原则上没有区别, 在讨论
数据结构时二者是通用的 。
(1) 所谓数据的逻辑结构是指数据元素之
间的逻辑关系 。
(2) 同一数据逻辑结构中的所有数据元素
都具有相同的特性是指数据元素所包含
的数据项的个数都相等 。
(3) 数据的逻辑结构与数据元素本身的内
容和形式无关 。
(4) 数据结构是指相互之间存在一种或多
种关系的数据元素的全体 。
(5) 从逻辑关系上讲, 数据结构主要分为
两大类：线性结构和非线性结构 。
试计算以下求和程序中所有语句的总
执行次数 。
float sum ( float a[ ],int n ) {
float s = 0.0; ---- 1
for ( int i = 0; i < n; i++ ) ---- n+1
s += a[i]; ---- n
return s; ---- 1
}
– ---- 2n+3
用大 O表示法给出程序的时间复杂性 。
void out ( float x[ ][ ],int m,int n ) {
float sum[ ]; O(1)
for ( int i = 0; i < m; i++ ) {
sum[i] = 0.0;
for ( int j = 0; j < n; j++ )
sum[i] = x[i][j]; O(m*n)
}
for ( int i = 0; i < m; i++ )
cout << "Line," << i << ":" <<
sum[i] << endl; O(m)
}
算法是一个有穷的指令集，它为解
决某一特定任务规定了一个运算序列。
它应当具有输入、输出,( ① )、有
穷性和可执行性等特性。算法效率的度
量分为 ( ② )和 ( ③ )。
( ② )主要通过在算法的某些部
位插装时间函数来测定算法完成某一规
定功能所需的时间。而 ( ③ )不实际
运行算法，它是分析算法中语句的执行
次数来度量算法的时间复杂性。
程序所需的存储空间包含两个部分
( ④ )和 ( ⑤ )。
( ④ )空间的大小与输入输出
数据的个数多少，数值大小无关；
( ⑤ )空间主要包括其大小与
问题规模有关的成分变量所占空间，
引用变量所占空间，以及递归栈所用
的空间，还有在算法运行过程中动态
分配和回收的空间。
例题
? 试编写一个函数计算 n!*2n 的值，结果
存放于数组 A[arraySize] 的第 n 个数组
元素中 (0 ? n ? arraySize)
? 若设计算机中允许的整数的最大值为
maxInt，则当 n > arraySize 或者对于某
一个 k ( 0 ? k ? n )，使得 k!*2k > maxInt
时，应按出错处理。
可有如下三种不同的出错处理方式：
?用 cerr << 及 exit (1) 语句来终止执行
并报告错误；
?用返回整数函数值 0,1 来实现算法,
以区别是正常返回还是错误返回；
?在函数的参数表设置一个引用型的整
型变量来区别是正常返回还是某中错误
返回 。
#include "iostream.h"
#define arraySize 100
#define MaxInt 0x7fffffff
int calc ( int T[ ],int n ) {
int i,value = 1;
if ( n != 0 ) {
for ( i = 1; i < n; i++) {
value *= i * 2;
if ( value > MaxInt / n / 2 )
return 0;
} //直接判断 i!*2i > MaxInt 是危险的
value *= n * 2;
}
T[n] = value; return 1; //n!*2n ? T[n]
}
void main ( ) {
int A[arraySize],i;
for ( i = 0; i < arraySize; i++ )
if ( !calc ( A,i ) ) {
cout << "failed at " << i << endl;
break;
}
}
? 抽象数据类型
? 算法定义
? 性能分析与度量
“学生”表格
学 号 姓 名 性别 籍 贯 出生年月
1 98 131 刘激扬 男 北 京 19 79.12
2 98 164 衣春生 男 青 岛 19 79.07
3 98 165 卢声凯 男 天 津 19 81.02
4 98 182 袁秋慧 女 广 州 19 80.10
5 98 224 洪 伟 男 太 原 19 81.01
6 98 236 熊南燕 女 苏 州 19 80.03
7 98 297 宫 力 男 北 京 19 81.01
8 98 310 蔡晓莉 女 昆 明 19 81.02
9 98 318 陈 健 男 杭 州 19 79.12
“课程”表格
课程编号 课 程 名 学时
024002 程序设计基础 64
024010 汇编语言 48
024016 计算机原理 64
024020 数据结构 64
024021 微机技术 64
024024 操作系统 48
024026 数据库原理 48
“选课单” 包含如下信息
学号 课程编号 成绩 时间
学生选课系统中实体构成的网状关系
学生
(学号,姓名,性别,籍贯 )
课程
(课程号,课程名,学分 )
选课
(学号,课程号,成绩 )
UNIX文件系统的系统结构图
/ (root)
bin lib user etc
math ds sw yin tao xie
Stack.cppQueue.cpp Tree.cpp
数据 （ data）
? 数据是信息的载体，是描述客观事物
的数、字符、以及所有能输入到计算
机中，被计算机程序识别和处理的符
号的集合。
? 数值性数据
? 非数值性数据
数据元素 (data element)
? 数据的 基本单位 。在计算机程序中常
作为一个整体进行考虑和处理。
? 有时一个数据元素可以由若干 数据项
(Data Item)组成。 数据项 是 具有独立
含义的最小标识单位 。
? 数据元素又称为元素、结点、记录。
数据对象 (data object)
? 数据对象是具有相同性质的数据元素
的集合。
?整数数据对象
N = { 0,?1,?2,… }
?学生数据对象
什么是数据结构
定义,
指某一数据对象的所有数据成员
之间的关系。记为：
Data_Structure = {D,R}
其中,D 是某一数据对象,R 是该
对象中所有数据成员之间的关系的有
限集合。
N 个网点之间的连通关系
树形关系 网状关系
1
5
2
4
36
1
5
2
4
36
数据结构 是数据的 组织形式
? 数据元素间的 逻辑关系,即数据的
逻辑结构 ；
? 数据元素及其关系在计算机存储内
的表示，即数据的 存储表示 ；
? 数据的运算，即对数据元素施加的
操作 。
数据的逻辑结构
? 数据的逻辑结构 从逻辑关系上描述
数据, 与数据的存储无关 ；
? 数据的逻辑结构可以看作是 从具体
问题抽象出来的数据模型 ；
? 数据的逻辑结构 与数据元素本身的
形式、内容无关 ；
? 数据的逻辑结构与数据元素的相对
位置无关。
数据的逻辑结构分类
? 线性结构
? 线性表
? 非线性结构
? 树
? 图（或网络）
线性结构
树形结构
树 二叉树 二叉搜索树
14131211
2 3 4
5 6 7 8 9 10 3
1 5
8
7
10
11
9
987
4 5 6
62 3 13
1
bin dev etc lib user
1
堆结构
,最大”堆, 最小”堆
12
3 5 4 8
7
11
10
2
9
16
4
10
1211
5
1
2
36
98
7
图结构 网络结构
1 2
5
6
4
3
1 2
5 4
3611
33
18
14
6
6
5
16
19
21
数据的存储结构
? 数据的存储结构是逻辑结构用计算
机语言的实现；
? 数据的存储结构依赖于计算机语言。
? 顺序存储表示
? 链接存储表示
? 索引存储表示
? 散列存储表示
抽象数据类型
? 数据类型
定义,一组性质相同的值的集合,以
及定义于这个值集合上的一组操作
的总称,
? C语言中的基本数据类型
char int float double void
字符型 整型 浮点型 双精度型 无值
? 构造数据类型由 基本数据类型 或 构
造数据类型 组成。
? 构造数据类型由 不同成分类型 构成。
? 基本数据类型可以看作是 计算机中
已实现的数据结构 。
? 数据类型就是数据结构，不过它是从编
程者的角度来使用的。
? 数据类型是模板，必须定义属于某种数
据类型的变量，才能参加运算。
抽象数据类型
(ADTs,Abstract Data Types)
?由用户定义，用以表示应用问题的
数据模型
?由 基本的数据类型 组成,并包括 一组
相关的服务 （或称操作）
?信息隐蔽 和 数据封装,使用与实现
相分离
抽
象
数
据
类
型
查找 登录 删除 修改
符 号 表
自然数的抽象数据类型定义
ADT NaturalNumber is
objects,一个整数的有序子集合,它开始于 0,
结束于机器能表示的最大整数 (MaxInt)。
Function,对于所有的 x,y ? NaturalNumber;
False,True ? Boolean,+,-,<,==,=等
都是可用的服务。
Zero( ), NaturalNumber 返回自然数 0
IsZero(x), if (x==0) 返回 True
Boolean else 返回 False
Add (x,y), if (x+y<=MaxInt)返回 x+y
NaturalNumber else 返回 MaxInt
Subtract (x,y), if (x < y) 返回 0
NaturalNumber else 返回 x - y
Equal (x,y), if (x==y) 返回 True
Boolean else 返回 False
Successor (x), if (x==MaxInt) 返回 x
NaturalNumber else 返回 x+1
end NaturalNumber
算法定义
? 定义,一个有穷的指令集,这些指令为
解决某一特定任务规定了一个运算序列
? 特性：
? 输入 有 0个或多个输入
? 输出 有一个或多个输出 (处理结果 )
? 确定性 每步定义都是确切、无歧义的
? 有穷性 算法应在执行有穷步后结束
? 有效性 每一条运算应足够基本
? 事例学习,选择排序问题
? 明确问题,递增排序
? 解决方案,逐个选择最小数据
? 算法框架：
for ( int i = 0; i < n-1; i++ ) { //n-1趟
从 a[i]检查到 a[n-1];
若最小整数在 a[k],交换 a[i]与 a[k];
}
? 细化程序,程序 SelectSort
算法设计 自顶向下，逐步求精
void selectSort ( int a[ ],int n ) {
//对 n个整数 a[0],a[1],…,a[n -1]按递增顺序排序
for ( int i = 0; i < n-1; i++ ) {
int k = i;
//从 a[i]查到 a[n-1],找最小整数,在 a[k]
for ( int j = i+1; j < n; j++ )
if ( a[j] < a[k] ) k = j;
int temp = a[i]; a[i] = a[k]; a[k] = temp;
}
}
性能分析与度量
? 算法的性能标准
? 算法的后期测试
? 算法的事前估计
算法的性能标准
? 正确性
? 可使用性
? 可读性
? 效率
? 健壮性
算法的后期测试
在算法中的某些部位插装时间函数
time ( )
测定算法完成某一功能所花费时间
顺序搜索 (Sequenial Search)
int seqsearch ( int a[ ],int n,int x ) {
//在 a[0],…,a[n -1]中搜索 x
int i = 0;
while ( i < n && a[i] != x )
i++;
if ( i == n ) return -1;
return i;
}
插装 time( ) 的计时程序
double start,stop;
time (&start);
int k = seqsearch (a,n,x);
time (&stop);
double runTime = stop - start;
printf (,%d%d\n ",n,runTime );
算法的事前估计
? 空间复杂度
? 时间复杂度
空间复杂度度量
? 存储空间的固定部分
程序指令代码的空间，常数、简单变量、
定长成分 (如数组元素、结构成分、对象
的数据成员等 )变量所占空间
? 可变部分
尺寸与实例特性有关的成分变量所占空
间、引用变量所占空间、递归栈所用空
间、通过 new和 delete命令动态使用空间
时间复杂度度量
? 运行时间 = 算法中每条语句执行时间之和。
? 每条语句执行时间 = 该语句的执行次数
（频度） * 语句执行一次所需时间。
? 语句执行一次所需时间取决于 机器的指令
性能和速度 和 编译所产生的代码质量,很
难确定。
? 设每条语句执行一次所需时间为单位时间，
则一个算法的运行时间就是该算法中所有
语句的频度之和。
例 求两个 n阶方阵的乘积 C = A?B
void MatrixMultiply ( int A[n][n],int B[n][n],
int C[n][n] ) {
for ( int i = 0; i < n; i++ ) … n+1
for ( int j = 0; j < n; j++ ) { … n(n+1)
C[i][j] = 0; … n2
for ( int k = 0; k < n; k++ ) … n2(n+1)
C[i][j] = C[i][j] + A[i][k] * B[k][j];
… n3
}
} 2n
3 + 2n2 + 2n +1
时间复杂度
? 算法中所有语句的频度之和是 矩阵阶数 n
的函数
T(n) = 2n3 + 2n2 + 2n +1
? 一般地，称 n 是问题的规模。则时间复
杂度 T(n) 是问题规模 n 的函数。
? 当 n趋于无穷大时，把时间复杂度的数量
级（阶）称为算法的渐进时间复杂度
T(n) = O(n3)
渐进时间复杂度
? 大 O表示法
? 加法规则 针对并列程序段
T(n,m) = T1 (n) + T2 (m)
= O(max (f (n),g (m)))
c < log2n < n < nlog2n < n2 < n3 <
2n < 3n < n!
变量计数
x = 0; y = 0;
for ( int k = 0; k < n; k ++ )
x ++;
for ( int i = 0; i < n; i++ )
for ( int j = 0; j < n; j++ )
y ++;
T1(n) = O(1)
T2(n) = O(n)
T3(n) = O(n2)
T(n) = T1(n)+T2(n)+T3(n) = O( max( 1,n,n2 ) )
= O(n2)
? 乘法规则 针对嵌套程序段
T (n,m) = T1 (n) * T2 (m)
= O(f (n)*g (m))
//起泡排序
void bubbleSort ( int A[n] ) {
//对表逐趟比较,n是表当前长度
int i = 1; exchange = 1;
while ( i < n && exchange ) {
BubbleExchange ( A,i,exchange );
i++;
} //一趟比较
}
void BubbleExchange( int A[n],int i ){
for ( int j = n -1; j >= i; j--)
if ( A[j-1] > A[j] ) {
int temp = A[j-1];
A[j-1] = A[j];
A[j] = temp;; //发生逆序,交换
}
}
渐进时间复杂度
O(f (n)*g (n)) = O(n2)
?
?
?
???1
1 2
1n
i
)n ( ni)(n?
BubbleSort n-1趟 T1(n) = O(n)
BubbleExchange ( )
n-i 次比较
? 有时,算法的时间复杂度不仅依赖于问题
规模 n，还与输入实例的初始排列有关。
? 在数组 A[n] 中查找给定值 k 的算法：
int i = n-1;
while ( i >= 0 && A[i] != k )
i--;
return i;
? 算法的语句 i-- 的频度不仅与 n 有关，
还与 A[ ] 中各元素的取值,以及 k 的取
值 有关。
? 例：设有两个算法在同一机器上运行，
其执行时间分别为 100n2和 2n，问：要
使前者快于后者,n至少要取多大？
解答：
问题是找出满足 100n2 <= 2n 的最小的
n。用试探法：
n = 13时,100n2 = 16900 > 2n = 8192
n = 14时,100n2 = 19600 > 2n = 16384
n = 15时,100n2 = 22500 < 2n = 32764
取 n = 15 满足要求。
填空例题
( ① )由某一数据对象和该对象
中各个数据成员间的关系组成。依据所
有数据成员之间关系的不同,( ① )
分为两大类,( ② )和 ( ③ )。
在 ( ② )中的各个数据成员依次
排列在一个线性序列中； ( ③ )的各
个数据成员不再保持在一个线性序列中，
每个数据成员可能与零个或多个其他数
据成员发生联系。
根据视点的不同，数据结构分为数
据的 ( ④ )和 ( ⑤ )。 ( ④ )是
面向问题的,( ⑤ )是面向计算机的。
判断下列叙述的对错 。 如果正确, 在题前
打, ?”, 否则打, ?” 。
(1) 数据元素是数据的最小单位 。
(2) 数据结构是数据对象与对象中数据元
素之间关系的集合 。
(3) 数据结构是具有结构的数据对象 。
(4) 数据的逻辑结构是指各数据元素之间
的逻辑关系, 是用户按使用需要建立的 。
(5) 算法和程序原则上没有区别, 在讨论
数据结构时二者是通用的 。
(1) 所谓数据的逻辑结构是指数据元素之
间的逻辑关系 。
(2) 同一数据逻辑结构中的所有数据元素
都具有相同的特性是指数据元素所包含
的数据项的个数都相等 。
(3) 数据的逻辑结构与数据元素本身的内
容和形式无关 。
(4) 数据结构是指相互之间存在一种或多
种关系的数据元素的全体 。
(5) 从逻辑关系上讲, 数据结构主要分为
两大类：线性结构和非线性结构 。
试计算以下求和程序中所有语句的总
执行次数 。
float sum ( float a[ ],int n ) {
float s = 0.0; ---- 1
for ( int i = 0; i < n; i++ ) ---- n+1
s += a[i]; ---- n
return s; ---- 1
}
– ---- 2n+3
用大 O表示法给出程序的时间复杂性 。
void out ( float x[ ][ ],int m,int n ) {
float sum[ ]; O(1)
for ( int i = 0; i < m; i++ ) {
sum[i] = 0.0;
for ( int j = 0; j < n; j++ )
sum[i] = x[i][j]; O(m*n)
}
for ( int i = 0; i < m; i++ )
cout << "Line," << i << ":" <<
sum[i] << endl; O(m)
}
算法是一个有穷的指令集，它为解
决某一特定任务规定了一个运算序列。
它应当具有输入、输出,( ① )、有
穷性和可执行性等特性。算法效率的度
量分为 ( ② )和 ( ③ )。
( ② )主要通过在算法的某些部
位插装时间函数来测定算法完成某一规
定功能所需的时间。而 ( ③ )不实际
运行算法，它是分析算法中语句的执行
次数来度量算法的时间复杂性。
程序所需的存储空间包含两个部分
( ④ )和 ( ⑤ )。
( ④ )空间的大小与输入输出
数据的个数多少，数值大小无关；
( ⑤ )空间主要包括其大小与
问题规模有关的成分变量所占空间，
引用变量所占空间，以及递归栈所用
的空间，还有在算法运行过程中动态
分配和回收的空间。
例题
? 试编写一个函数计算 n!*2n 的值，结果
存放于数组 A[arraySize] 的第 n 个数组
元素中 (0 ? n ? arraySize)
? 若设计算机中允许的整数的最大值为
maxInt，则当 n > arraySize 或者对于某
一个 k ( 0 ? k ? n )，使得 k!*2k > maxInt
时，应按出错处理。
可有如下三种不同的出错处理方式：
?用 cerr << 及 exit (1) 语句来终止执行
并报告错误；
?用返回整数函数值 0,1 来实现算法,
以区别是正常返回还是错误返回；
?在函数的参数表设置一个引用型的整
型变量来区别是正常返回还是某中错误
返回 。
#include "iostream.h"
#define arraySize 100
#define MaxInt 0x7fffffff
int calc ( int T[ ],int n ) {
int i,value = 1;
if ( n != 0 ) {
for ( i = 1; i < n; i++) {
value *= i * 2;
if ( value > MaxInt / n / 2 )
return 0;
} //直接判断 i!*2i > MaxInt 是危险的
value *= n * 2;
}
T[n] = value; return 1; //n!*2n ? T[n]
}
void main ( ) {
int A[arraySize],i;
for ( i = 0; i < arraySize; i++ )
if ( !calc ( A,i ) ) {
cout << "failed at " << i << endl;
break;
}
}
