kl800.com省心范文网

第1章 绪论2_图文

?1.3 算法分析
?1.3.1 算法设计的目标

?(1)正确性。
?(2)可使用性。 ?(3)可读性。 ?(4)健壮性。 ?(5)高效率与低存储量需求。

?1.3.2 算法效率分析 ? 求解同一问题可能对应多种算法,例如求s=1+2+…+n, 其中n为正整数,通常有以下两种算法fun1(n)和fin2(n),显然 前者算法的时间效率不如后者。
int fun1(int n) { int i,s=0; for (i=1;i<=n;i++) s+=i; return s; } int fun2(int n) { int s; s=(n*(n+1)/2; return s; }

? 一个算法是由控制结构(顺序、分支和循环3种)和原操 作(指固有数据类型的操作)构成的,算法的运行时间取决于 两者的综合效果。 ? 例如,如下所示是在某个类中定义的 Solve方法,其中形 参a是一个m行n列的数组,当是一个方阵(m=n)时求主对角 线所有元素之和并返回 true,否则返回false,从中看到该算法 由4部分组成,包含两个顺序结构、一个分支结构和一个循环 public bool Solve(int m,int n,double [,] a, ref double s) 结构。 {
int i; s = 0; if (m != n) return false; for (i = 0; i < m; i++) s += a[i, i]; return true; } 顺序结构

分支结构

循环结构 顺序结构

? 为了便于比较求解同一问题的不同算法,通常的做法是, 从算法中选取一种对于所讨论的问题来说是基本运算的原操 作,算法执行时间大致为这种原操作所需的时间与其运算次 数(一个语句的运行次数称为语句频度)的乘积。被视为算 法基本运算的原操作一般是最深层循环内的语句(Solve算法 中的基本运算为s+=a[i,i])。 ? 显然,在一个算法中,执行基本运算的原操作的次数越 少,其运行时间也就相对地越少;反之其运行时间也就相对 地越多。也就是说,一个算法的执行时间可以看成是其中基 本运算的原操作的执行次数。

? 一个算法的执行基本运算次数T(n)是问题规模n的某个函 数f(n),记作: ? T(n)=O(f(n))

?记号“ O”读作“大O”(是Order的简写,意指数量级),它 表示随问题规模n的增大算法执行时间的增长率和f(n)的增长率 相同。 ? “ O” 的形式定义为:若 f(n) 是正整数 n 的一个函数,则 T(n)=O(f(n))表示存在一个正的常数 c和n0,使得当n≥n0时都满 足 T(n)≤cf(n) ,也就是只求出 T(n) 的最高阶,忽略其低阶项和 常系数,这样既可简化T(n)的计算,又能比较客观地反映出当 n很大时,算法的时间性能,例如: ? T(n)=3n2-5n+100=O(n2)

? 一个没有循环的算法中基本运算次数与问题规模 n 无关, 记作 O(1) ,也称作常数阶。一个只有一重循环的算法中基本 运算次数与问题规模n的增长呈线性增大关系,记作O(n),也 称线性阶。其余常用的还有平方阶O(n2)、立方阶O(n3)、对数 阶O(log2n)、指数阶O(2n)等等。各种不同数量级对应的值存在 着如下关系: ? O(1)<O(log2n)<O(n)<O(nlog2n)<O(n2)<O(n3)<O(2n)<O(n!)

?【例 1.8】 求两个 n阶方阵的相加 C=A+B 的算法如下,分析 其时间复杂度。
?public void matrixadd(int n, int A [,],intB [,],intC [,]) ?{ int i,j;

?
? ?

for (i=0;i<n;i++)
for (j=0;j<n;j++) C[i,j]=A[i,j]+B[i,j];

//语句①
//语句② //语句③

?}

? 解法1:累计算法中所有语句的执行次数 T(n),再来求算 法的时间复杂度。该算法包括 3个可执行语句①、②和③。其 中语句①循环控制变量 i要从0增加到n,测试i=n时才会终止, 故它的频度是n+1,但它的循环体却只能执行n次。
? 语句②作为语句①循环体内的语句应该只执行n次,但语 句②本身也要执行n+1次,所以语句②频度是n(n+1)。

? 同理可得语句③的频度为 n2。因此,该算法中所有语句 频度之和为:
? T(n)=n+1+n(n+1)+n2=2n2+2n+1=O(n2)

解法 2 :该算法中的基本运算是两重循环中最深层的语句 C[i][j]=A[i][j]+B[i][j],分析它的频度,即: T(n)= ?? 1 ? ? n ?n? 1 ? n * n ? n2
i ?0 j ?0 i ?0 i ?0 n ?1 n ?1 n ?1 n ?1

=O(n2)

例1.5
{

分析以下算法的时间复杂度。

int fun(int n)

int i,j,k,s;
s=0; for (i=0;i<=n;i++) for (j=0;j<=i;j++) for (k=0;k<=j;k++) s++; return(s); 基本语句或基本操作

}

解:该算法的基本操作是语句 s++,其频度: j n i T(n)= =O(n3) 则该算法的时间复杂度为O(n3)。

??? 1
i ?0 j ?0 k ?0

例1.6
{

分析以下算法的时间复杂度。

void func(int n) int i=0,s=0; while (s<n) { i++; 基本语句

s=s+i;
} }

解:对于while循环语句,设执行的次数为m,i从0 开始递增1,直到m为止,有:

s=0+1+2+…+(m-1)=m(m-1)/2,
并满足s=m(m-1)/2<n,则有m< 。 T(n)=O( )

所以,该算法的时间复杂度为O( )。

例1.7 有如下算法:
void fun(int a[],int n,int k) //数组a共有n个元素 { int i; if (k==n-1) for (i=0;i<n;i++) //n次 printf("%d\n",a[i]); else { for (i=k;i<n;i++) //n-k次 a[i]=a[i]+i*i; fun(a,n,k+1); } }

调用上述算法的语句为fun(a,n,0),求其时间复杂度。

解:设 fun(a,n,0) 的时间复杂度为 T(n) ,则 fun(a,n,k) 的执 行时间为T1(n,k),由fun()算法可知: T1(n,k)=n 当k=n-1时

T1(n,k)= (n-k)+T1(n,k+1)


其他情况

T(n)=T1(n,0)=n+T1(n,1)=n+(n-1)+T1(n,2) =…=n+(n-1)+…+2+T1(n,n-1) =n+(n-1)+ …+2+n =O(n2) 所以调用fun(a,n,0)的时间复杂度为O(n2)。

1.3.3 算法空间复杂度分析
空间复杂度是对一个算法在运行过程中临时占用的存储空间 大小的量度,一般也作为问题规模n的函数,以数量级形式给出, 记作: S(n) = O(g(n)) 若所需额外空间相对于输入数据量来说是常数,则称此算法 为原地工作。若所需存储量依赖于特定的输入,则通常按最坏 情况考虑。

例1.12 分析例1.8和例1.9的空间复杂度。 解:由于这两个算法中临时变量的个数与问题规模 n无关,所以空间复杂度均为O(1)。

1.4 数据结构+算法=程序
《数据结构+算法=程序》的作者:
N.Wirth(1934年~),瑞士计算机科学家,1960 年获加利福尼亚大学伯克利分校博士学位。曾任 斯坦福大学、苏黎世联邦理工学院教授。发明多 种 计 算 机 语 言 ( 包 括 Pascal 、 Modula 和 Oberon 等),并为软件工程领域作出过开拓性的贡献。 于 1980 年 获 得 计 算 机 科 学 界 最 高 奖 - 图 灵 奖 (http://en.wikipedia.org/wiki/Turing_Award)。

Wirth的学生: C#语言创始人:Anders Hejlsberg(安德斯,海斯博 格)

数据结构领域做出突出贡献的计算机科学家:
Donald Knuth(1938年~),算法和程序设 计 技 术 的 先 驱 者 , 计 算 机 排 版 系 统 TEX 和 METAFONT的发明者,他因这些成就和大量 创造性的影响深远的著作(19部书和160篇论 文)而誉满全球。作为斯坦福大学计算机程 序设计艺术的荣誉退休教授,他当前正全神 贯注于完成其关于计算机科学的史诗性的七 卷集。这一伟大工程在 1962 年他还是加利福 尼亚理工学院的研究生时就开始了。他于 1974年获得计算机科学界最高奖-图灵奖。

C.A.R.Hoare(1934年~),英国计算机科学 家,毕业于牛津大学,他最重要的工作包括: 快速排序算法,Hoare逻辑,形式语言通信时 序进程( CSP )等。于 1980 年获得计算机科 学界最高奖-图灵奖。

1.4.1 程序和数据结构
沃思指出:程序就是在数据的某些特定的表示方法 和结构的基础上,对抽象算法的具体表述,所以说程序 离不开数据结构。

1.4.2 算法和程序
由程序设计语言描述的算法就是计算机程序。对一个 求解问题而言,算法就是解题的方法,没有算法,程 序就成了无本之末,无源之水。 有了算法,将它表示成程序是不困难的。算法是程序 的核心。算法在程序设计,也可以说软件开发,甚至 可以说在整个计算机科学中的地位都是极其重要的。

1.4.3 算法和数据结构
求解的问题可以通过抽象数据类型描述,它由数据的 逻辑结构和抽象运算两部分组成。
一种数据的逻辑结构可以映射成多种存储结构,抽象 运算在不同的存储结构上实现可以对应多种算法,在 同一种存储结构上实现也可能有多种算法,通过算法 的时间复杂度和空间复杂度等分析,可以得到好的算 法。

抽象数据类型 = 数据的逻辑结构

+ 抽象运算(运算的功能描述)

数据的存储结构 1

……

数据的存储结构 n

抽象运算的实现

算法 11

… 算法 1m

……

算法 n1 … 算法分析

算法 nm

好的算法

好算法与以下因素有关: 算法的正确性、可读性和可维护性等。 算法的时间和空间复杂度。

数据存储结构会影响算法的好坏,因此在选择存储结构 时,也要考虑其对算法的影响。存储结构对算法的影响主 要在两方面:
存储结构的存储能力。如果存储结构存储能力强、存储 信息多,算法将会较好设计。反之对于过于简单的存储 结构,可能就要设计一套比较复杂的算法。在这一点上, 经常体现时间与空间的矛盾,往往存储能力是与所使用 的空间大小成正比的。

存储结构应与所选择的算法相适应。存储结构是实现算 法的基础,也会影响算法的设计,其选择要充分考虑算 法的各种操作,应与算法的操作相适应。

一个典型示例
问题描述:有若干学生数据(学生数小于50), 每个学生数据包含学号(每个学生学号是唯一的, 但学生记录不一定按学号顺序存放)、姓名、班 号和若干门课程成绩(每个学生所选课程数目可 能不等,但最多不超过6门)。 要求:设计一个程序输出每个学生的学号、姓名 和平均分以及每门课程(课程编号从1~6)的平 均分。

设计方案1:将学生的全部数据项放在一个表中,一 个学生的全部数据对应一条记录。由于课程最多可选6门, 对应的成绩项也应有6个。对应的数据结构如下:
struct stud { int no; char name[10]; int bno; int deg1; int deg2; int deg3; int deg4; int deg5; int deg6; }; //学号 //姓名 //班号 //课程1分数 //课程2分数 //课程3分数 //课程4分数 //课程5分数 //课程6分数

存储结构1

no 1 8 …

name 张斌 刘丽 …

bno 9901 9902 …

deg1 78 65 …

deg2 82 -1 …

deg3 -1 72 …

deg4 92 -1 …

deg5 85 80 …

deg6 83 79 …

设计方案1的特点:

存储空间:中(若学生没有选该课程,对应空间仍存在)
算法时间:少 算法简洁性差:算法完全依赖数据结构

设计方案2:将学生的全部数据项放在一个表中,但一 个学生的一门课程成绩对应一条记录。这样成绩项只需要 一个,为了区分不同课程成绩,需增加一个课程编号项。 对应的数据结构如下:
struct stud { int no; char name[10]; int bno; int cno; int deg; };

//学号 //姓名 //班号 //课程编号 //课程分数

存储结构2

no 1 1 1 1 1 8 8 8

name 张斌 张斌 张斌 张斌 张斌 刘丽 刘丽 刘丽

bno 9901 9901 9901 9901 9901 9902 9902 9902

cno 1 2 4 5 6 1 3 5

deg 78 82 92 85 83 65 72 80

8


刘丽


9902


6


79


设计方案2的特点: 存储空间:大 算法时间:多 算法简洁性:好

设计方案3:将学生的学号、姓名和班号放在一个表中, 将成绩数据放在另一个表中,两者通过学号关联。前者一 个学生对应一个记录,后者一门课程成绩对应一条记录。 对应的数据结构如下:
struct stud1 { int no; char name[10]; int bno; }; struct stud2 { int no; int cno; int deg; };

//学号 //姓名 //班号

//学号 //课程编号 //分数

存储结构3

no

cno 1 2 4 5 6 1

deg 78 82 92 85 83 65

关联 no name bno

1 1 1 1 1 8

1
8

张斌
刘丽

9901
9902







8
8 8 …

3
5 6 …

72
80 79 …

设计方案3的特点: 存储空间:少。 算法时间:中。 算法简洁性:好。
综合分析的结果

最佳方案

思考题: 学习第1章有什么体会?

本章小结
本章介绍了数据结构的基本概念,主要学习要点如下:

(1)数据结构的定义,数据结构包含的逻辑结构、存储 结构和运算三方面的相互关系。
(2)各种逻辑结构即线性结构、树形结构和图形结构之 间的差别。

(3)数据结构和数据类型的差别和联系。

(4)算法的定义及其特性。
(5)算法的时间复杂度和空间复杂度分析。

上机题:

熟悉VC++6.0环境

参数相关知识
本书中采用C/C++语言描述算法。

说明:C++语言中提供了一种引用运算符“&”,引用 是个别名,当建立引用时,程序用另一个已定义的变量 或对象(目标)的名字初始化它,从那时起,引用作为 目标的别名而使用,对引用的改动实际就是对目标的改 动。
注意:Turbo C不支持引用类型,VC++、Dev C++支 持引用类型。

编写一个函数swap1(x,y),当执行语句swap1(a,b)时,交 换a和b的值。
void swap1(int x,int y) { int tmp;

tmp=x;x=y;y=tmp;
}

注意:a和b的值不会发生了交换。

为此,采用指针的方式来回传形参的值,需将上述函数 改为:
void swap2(int { int tmp; tmp=*x; *x=*y; *y=tmp; } *x,int *y)
//将x的值放在tmp中 //将x所指的值改为*y //将y所指的值改为tmp

上述函数的调用改为swap2(&a,&b),显然远不如采用引 用方式简洁。所以本书后面很多算法都采用引用形参。

“引用”的概念
例如:
int a=4; int &b=a; //a为普通的整型变量 //b是a的引用变量

这里说明b变量是变量a的引用,b也等于4,之后这两

个变量同步改变。当a改变时b也同步改变,同样,当b改
变时a也同步改变。

void main() { int a=2; int &b=a;

printf("a=%d,b=%d\n",a,b);
b++; printf("a=%d,b=%d\n",a,b);

//输出:a=2,b=2

//输出:a=3,b=3

a++;
printf("a=%d,b=%d\n",a,b); } //输出:a=4,b=4

引用常用于函数形参中,采用引用型形参时,在函数调用

时将形参的改变回传给实参,例如,有如下函数(其中的形参
均为引用型形参):
void swap(int &x,int &y) //形参前的“&”符号不是指针运算符 { int tmp=x; x=y;y=tmp }

当用执行语句swap(a,b)时,a和b的值发生了交换。

普通的参数传递
void fun1(int n) { int m=2; fun2(m); printf(“%d\n”,m); } 实参到形参单向 值传递 fun1(m) fun2(x) 实参

void fun2(int x)
{ x++; 普通形参

printf(“%d\n”,x);

}

引用类型的参数传递
void fun1(int n)
{ int m=2; fun2(m); 实参 void fun2(int &x) { x++;

引用型形参

printf(“%d\n”,x); }

printf(“%d\n”,m);
}

实参到形参单向 值传递 fun1(m) fun2(x) 形参回传给实参,实参和 形参可步发生改变

用C/C++描述算法示例 例1.3 编写一个算法, 读入三个整数x、y和z的值,要求从大 到小输出这三个数。 解:依次输入x、y和z这三个整数,通过比较交换后,使得 x≥y≥z,然后输出x、y和z。 在算法中应考虑对这三个元素作尽可能少的比较和移动, 如下述算法在最坏的情况下只需进行3次比较和7次移动。

void Descending() { printf("输入x,y,z"); scanf("%d,%d,%d",&x,&y,&z); if (x<y) { temp=x; x=y;y=temp;//交换x,y,使x>=y } if (y<z) { temp=z; z=y; //使temp>z if (x>=temp) y=temp; else { y=x;x=temp; } } printf("%d,%d,%d\n",x,y,z); }


第1章_绪论2_图文.ppt

第1章_绪论2 - 交通管理与控制 南京工业大学交通运输工程学院 1 1 主讲教

第1章绪论-2汇总_图文.ppt

第1章绪论-2汇总 - macromolecle chemistry 高分子化学 教材:《高分子化学》潘祖仁主编 第2讲 主讲教师:李敬芬 40h 1.3 高分子化合物的分类和命名 1.分...

第1章 绪论-2要点_图文.ppt

第1章 绪论-2要点 - 第1章 绪论 补充:频道和信道的概念 频道:指的是一定

第1章绪论(2)_图文.ppt

第1章绪论(2) - 1.1 数据结构的定位 1.2 基本概念 1.3 算法和算法的分析 1 1.2 基本概念 一、数据与数据结构 、数据类型 三、抽象数据类型 2 、...

第1章 绪论2_图文.ppt

第1章 绪论2 - 第一章 绪论 1.1 什么是数据结构 1.2 基本概念和术语

数据结构第1章 绪论2_图文.ppt

数据结构第1章 绪论2_计算机软件及应用_IT/计算机_专业资料。第一章 绪论

第1章 绪论(第2版)模板_图文.ppt

第1章 绪论(第2版)模板 - 第1章 绪论 编码理论 授课教师:王珂 所属院系:电子信息工程系 第1章 绪论 编码理论课程简介 课程的基本情况 课程的教材和参考书 ...

园林艺术第1章 绪论2剖析_图文.ppt

园林艺术第1章 绪论2剖析 - 资源与环境学院 园林艺术 主讲:刘惠 grlea

第1章绪论第2章生物质能特点_图文.ppt

第1章绪论2章生物质能特点 - 文档均来自网络,如有侵权请联系我删除文档... 第1章绪论2章生物质能特点_物理_自然科学_专业资料。文档均来自网络,如有侵权请联系...

第一章 绪论(2)_图文.pdf

第一章 绪论(2) - 第一章 绪论 第三节 出版业经营管理 ? 所谓出版业经营

第1章绪论-2010-12-2_图文.pdf

第1章绪论-2010-12-2 - 第1章 绪论 1.1 钢结构的发展概况 钢结

机器人学基础-第1章-绪论2_图文.ppt

机器人学基础-第1章-绪论2 - 1.1Development of Robot

传感器技术-第1章 绪论2_图文.ppt

传感器技术-第1章 绪论2 - 1.3.5 系统误差 1. 系统误差的发现 2.

第一章 绪论 2_图文.ppt

第一章 绪论 2 - 道路勘测设计 赵永平 唐勇 主编 高等教育出版社 山东交通学院 第1章 绪 论 第二讲 通过本次课的学习,学生应重点掌握:公路 和城市道路的...

第1章绪论2_图文.ppt

第1章绪论2 - 通 信 第一章 原 绪论 理 内容回顾 信息源 发送设备 信道 接收设备 受信者 发送端 噪声源 接收端 第一章 绪论 2 通信方式 定义: ...

哈工大数据结构第1章-绪论 (2)_图文.ppt

哈工大数据结构第1章-绪论 (2) - 数据结构与算法 刘扬 哈尔滨工业大学 计算机学院 1 课程简介(1/2) 课程编号:T050307 英文译名:DATA STRUCTURE and...

第1章 绪论 第2版 周分析_图文.ppt

第1章 绪论2版 周分析 - 第1章 绪论 为什么要学习数据结构 ?编程基础

第一章 分析化学绪论2_图文.ppt

第一章 分析化学绪论2 - Chapter 1 概论 1.5 定量分析化学概论

第1章 数据库系统绪论(2)_图文.ppt

数据库原理与应用大外软件学院计算机教研室杨晨 1 第1章 数据库系统绪论 1.1

第1章 绪论2_图文.ppt

第1章 绪论2 - ?1.3 算法分析 ?1.3.1 算法设计的目标 ?(1)正