从问题到程序

《从问题到程序》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、从问题到程序——算法2007/03/05Review：DataStructure:Anorganizationofinformation,usuallyinmemory,forbetteralgorithmefficiency,suchasqueue,stack,linkedlist,heap,dictionary,andtree.Itmayincluderedundantinformation,suchaslengthofthelistornumberofnodesinasubtree.AbstractDataType(ADT)Asetofdatavaluesandassociatedope

2、rationsthatarepreciselyspecifiedindependentofanyparticularimplementation.Note:Sincethedatavaluesandoperationsaredefinedwithmathematicalprecision,ratherthanasanimplementationinacomputerlanguage.从问题到程序——算法什么是算法算法分析技术算法设计技术递归算法什么是算法：对一个问题求解的确定性的方法与步骤。X–6y=02x+y=13数据表达(存储)+数据运算程序数据结构+算法程序Algorithmsand

3、ProgramsAlgorithm:amethodoraprocessfollowedtosolveaproblem.Amappingofinputtooutput（OrTransformationfrominputtooutput）Aproblemcanhavemanyalgorithms.算法的基本要求有穷性：对于一个具体的问题算法必须保证执行有限步之后结束。确切性：算法的每一步骤必须意义明确。无歧义。输入输出：一个算法有0个或多个输入输入。可行性：算法原则上能够实现并精确地运行。算法的基本要求（续）评价一个好的算法有以下几个标准:(1)正确性(Correctness)算法应满足具体问题的

4、需求。(2)可读性(Readability)算法应该好读。每一步骤以及步骤间的关系清晰可读。(3)健状性(Robustness)算法应具有容错处理。当输入非法数据时，算法应对其作出反应，而不是产年莫名其妙的输出结果(4)效率与存储量需求效率指的是算法执行的时间；存储量需求指算法执行过程中所需要的最大存储空间。一般，这两者与问题的规模有关。例子1：插入排序算法（摸牌）数据结构设计：intcard[MAXNUM];?算法设计：5,2,4,10,75,2,5,2,4,5,2,4,5,10,2,4,5,7,10例子1：插入排序算法（续）算法与数据结构的关系算法的实现要依赖于特定的数据结构数据结构不同，

5、实现同样的功能算法也就不同不同的数据结构的特点会反映到算法实现的效率和其他特性。（作业：将上面的插入排序算法改由链表实现。）算法+数据结构=程序算法的正确性算法的正确性：以一组满足初始条件的输入开始执行，该算法的执行一定终止，并且能够得到满足要求的结果调试：调试只能发现和减少错误，不能保证正确。边界条件与异常处理是软件开发的重要环节。（在作业中增加边界条件控制：输入数据必须为1-13之间的整数，否则提示重新输入。）算法性能分析与度量?算法的性能标准?正确性，可使用性，可读性，效率，健壮性?算法的后期测试?在算法中的某些部位插装时间函数time()测定算法完成某一功能所花费时间?算法的事前估计?

6、空间复杂度?时间复杂度时间复杂度（事先估计）编译时间?运行时间?程序步?语法上或语义上有意义的一段指令序列?执行时间与指令特性无关?例如：声明语句：程序步数为0;表达式：程序步数为1算法中重复执行的操作次数反映算法的时间复杂度。算法的时间复杂度（事先估计）算法增长趋势分析与大O表示法算法的最坏情况与平均情况分析：算法复杂性为O(f(n))，如果存在正的常数c和n0，当问题的规模n≥n0后，该算法的复杂性T(n)≤c·f(n)。这时也称该算法的复杂性增长为f(n)。时间复杂性分析属于抽象分析，不考虑计算机硬件实际的快慢。时间复杂度的数量级(阶):常数阶O(1)对数阶O(log2n)线性阶O(n)

7、线性对数阶O(nlog2n)平方阶O(n2)立方阶O(n3)……指数阶O(2n)多项式阶例2：分析以下程序段的时间复杂度。?i=1；(1)?while(i<=n)?i=i*2；(2)(1)1(2)？空间复杂度度量?存储空间的固定部分程序指令代码的空间，常数、简单变量、定长成分变量所占空间。算法所需辅助空间都只是若干简单变量，和问题规模无关。这类所需额外空间相对于输入数据量来说是常量的算法，被称作是