算法分析与设计教程文件.doc

算法分析与设计教程文件.doc

ID:61937871

大小:122.00 KB

页数:7页

时间:2021-03-31

算法分析与设计教程文件.doc_第1页
算法分析与设计教程文件.doc_第2页
算法分析与设计教程文件.doc_第3页
算法分析与设计教程文件.doc_第4页
算法分析与设计教程文件.doc_第5页
资源描述:

《算法分析与设计教程文件.doc》由会员上传分享,免费在线阅读,更多相关内容在工程资料-天天文库

1、__________________________________________________第一章什么是算法 算法是解决一个计算问题的一系列计算步骤有序、合理的排列。对一个具体问题(有确定的输入数据)依次执行一个正确的算法中的各操作步骤,最终将得到该问题的解(正确的输出数据)。算法的三个要素 1).数据:运算序列中作为运算对象和结果的数据. 2).运算:运算序列中的各种运算:赋值,算术和逻辑运算 3).控制和转移:运算序列中的控制和转移.算法分类从解法上:数值型算法:算法中的基本运算为算术运算;非数值型算法:算法中的基本

2、运算为逻辑运算.从处理方式上:串行算法:串行计算机上执行的算法;并行算法:并行计算机上执行的算法算法的五个重要的特性(1)有穷性:在有穷步之后结束。 (2)确定性:无二义性。(3)可行性:可通过基本运算有限次执行来实现。 (4)有输入表示存在数据处理 (5)有输出伪代码 程序设计语言(PDL),也称为结构化英语或者伪代码,它是一种混合语言,它采用一种语言(例如英语)的词汇同时采用类似另外一种语言(例如,结构化程序语言)的语法。____________________________________________________

3、________________________________________________特点:1)使用一些固定关键词的语法结构表达了结构化构造、数据描述、模块的特征; 2)以自然语言的自由语法描述了处理过程;3)数据声明应该既包括简单的也包括复杂的数据结构;4)使用支持各种模式的接口描述的子程序定义或者调用技术。 求两个n阶方阵的相加C=A+B的算法如下,分析其时间复杂度。 #defineMAX20//定义最大的方阶 voidmatrixadd(intn,intA[MAX][MAX], intB[MAX][MAX],in

4、tC[MAX][MAX]) {inti,j; for(i=0;i

5、+(m-1)=m(m-1)/2,并满足s=m(m-1)/2

6、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)+…__________________________________________________________________________________________

7、__________+2+n   =O(n2)所以调用fun(a,n,0)的时间复杂度为O(n2)。估计如下二重循环算法在最坏情况下时间复杂性T(n)的阶。fori:=1tondo forj:=1toido {s1,s2,s3,s4};s1,s2,s3,s4为单一赋值语句 分析:内循环体只需O(1)时间,故 内循环共需外循环共需渐进分析 时间复杂性渐进阶分析的规则:(最坏情况) 1).赋值,比较,算术运算,逻辑运算,读写单个变量(常量)只需1单位时间 2).执行条件语句ifcthenS1elseS2的时间为TC+max(TS1,

8、TS2). 3).选择语句caseAofa1:s1;a2:s2;...;am:sm 需要的时间为max(TS1,TS2,...,TSm). 4).访问数组的单个分量或纪录的单个域需要一个单位时间. 5).执行for循环语句的时间=执行循环体时间*循环次数. 6)

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。