算法设计与分析 复习

《算法设计与分析 复习》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、算法设计与分析复习算法与程序算法：解决问题的方法或过程，是满足下述性质的指令序列。输入：有零个或多个外部量作为算法的输入。输出：算法产生至少一个量作为输出。确定性：组成算法的每条指令清晰、无歧义。有限性：算法中每条指令的执行次数有限，执行每条指令的时间也有限。程序：程序是算法用某种程序设计语言的具体实现。程序可以不满足算法的性质(4)即有限性。例如操作系统，是一个在无限循环中执行的程序，因而不是一个算法。操作系统的各种任务可看成是单独的问题，每一个问题由操作系统中的一个子程序通过特定的算法来实现。该子程序得到输出结果后便终止。描述算法与算法设计算法分析的基本原则

2、算法分析的基本原则时间复杂度(timecomplexity)T(n)时间复杂度指程序执行时所用的时间。在使用解析方法时程序p的时间复杂度表示为输入量的函数T。机器独立的分析方法-解析的方法.在解析地分析时间复杂度时,使用以下两种时间单位并计算：操作计数(operationcount):算法的基本操作(程序)步计数(stepcount):分析全部程序要点:基本操作或程序步的执行时间必须是常数。最好，最坏和平均情形时间复杂度当长度相同的不同输入有不同的计算时间时，时间复杂度分析分别考虑三种情形：即最好，最坏和平均.当应用对计算时间有严格要求时，应做最坏情形分析-up

3、perbound.最好情形分析给出一个算法的计算时间的下界，用来否定一个算法.渐近分析,符号(О,Ω,Θ)计算机科学使用最多的符号-讨论算法时使用的共同语言.渐近分析-随n的增加T(n)的增长率渐近分析(续)大Ωf(n)=Ω(g(n))iff存在常数c和n0使得对所有n>n0,有f(n)>cg(n)成立.渐近分析(续)称g(n)为f(n)的渐近下界例如,f(n)=0.001n2-10n-1000=Ω(n2)因为:limf(n)/n2=0.001渐近分析(续)符号Θ如果f(n)=O(g(n))同时f(n)=Ω(g(n))则f(n)=Θ(g(n)),并称f(n)与g

4、(n)同阶.Limf(n)/g(n)=c,0

5、程的产生。分治与递归像一对孪生兄弟，经常同时应用在算法设计之中，并由此产生许多高效算法。2.1递归的概念例1阶乘函数阶乘函数可递归地定义为：2.1递归的概念例2Fibonacci数列无穷数列1，1，2，3，5，8，13，21，34，55，…，被称为Fibonacci数列。它可以递归地定义为：2.1递归的概念例4排列问题设计一个递归算法生成n个元素{r1,r2,…,rn}的全排列非递归算法：字典序法[例]字符集{1,2,3},较小的数字较先,这样按字典序生成的全排列是:123,132,213,231,312,321。2.1递归的概念例5整数划分问题将正整数n表示成

6、一系列正整数之和：n=n1+n2+…+nk，其中n1≥n2≥…≥nk≥1，k≥1。正整数n的这种表示称为正整数n的划分。求正整数n的不同划分个数。例如正整数6有如下11种不同的划分：6；5+1；4+2，4+1+1；3+3，3+2+1，3+1+1+1；2+2+2，2+2+1+1，2+1+1+1+1；1+1+1+1+1+1。递归小结优点：结构清晰，可读性强，而且容易用数学归纳法来证明算法的正确性，因此它为设计算法、调试程序带来很大方便。缺点：递归算法的运行效率较低，无论是耗费的计算时间还是占用的存储空间都比非递归算法要多。递归小结解决方法：在递归算法中消除递归调用，

7、使其转化为非递归算法。1.采用一个用户定义的栈来模拟系统的递归调用工作栈。该方法通用性强，但本质上还是递归，只不过人工做了本来由编译器做的事情，优化效果不明显。2.用递推来实现递归函数。3.通过Cooper变换、反演变换能将一些递归转化为尾递归，从而迭代求出结果。后两种方法在时空复杂度上均有较大改善，但其适用范围有限。分治法的适用条件分治法所能解决的问题一般具有以下几个特征：该问题的规模缩小到一定的程度就可以容易地解决；该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质利用该问题分解出的子问题的解可以合并为该问题的解；该问题所分解出的各个子问题

8、是相互独立的，即子问题之