离散数学-算法

《离散数学-算法》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、离散数学黄晓宇HuangSir@china.com.cn本讲内容算法简介算法例子算法分析递归算法算法－一组有限的指令集合输入：算法接受输入。输出：算法产生输出。精确性：步骤被精确描述。确定性：每步执行的结果是惟一的，且只依赖于输入和前面步骤执行的结果。有限性：算法可以终止，也就是在执行有限多条指令后停止。正确性：算法生成的输出结果是正确的，也就是算法可以正确地求解问题。一般性：算法适应于一组输入。算法示例－三数排序1.large=a.2.Ifb>large,thenlarge=b.3.Ifc>lar

2、ge,thenlarge=c.这个算法的思想是对这些数一个一个地检查，将所见的最大数赋值给变量large。在算法停止时，large就等于这三个数中最大的了跟踪a=1,b=5,c=3a=1,b=5,c=91.large=a.2.Ifb>large,thenlarge=b.3.Ifc>large,thenlarge=c.x=算法正确性证明算法描述：在数列s1,...,sn中找出最大的一个。输入：s,n输出：large（序列s中的最大值）max(s,n){large=s1fori=2tonif(si>la

3、rge)large=sireturnlarge}算法正确性证明（二）循环不变式：在循环的每次迭代前后均为真的谓词large=max{s1,...,sn}算法正确性证明（三）－归纳平凡情况（i=1）large是序列中的最大值。假设large是子序列s1,...,si中的最大值。假如ilarge，赋值large＝si+1；（2）si+1≤large，算法不改变large的值。因此，large=max{s1,...,sn}是一个循环不变量。for循环在i=n时结束，

4、算法正确。文本搜索假设给定一个文本t（例如一个文档），在t中找出特定词组p首次出现的位置。ABCABCDEAD……EDCEDCEDCEDCtext_search(p,m,t,n){fori=1ton-m+1{j=1;while(ti+j-1==pj){j=j+1;if(j>m)returnj;}}return0}插入排序假设插入排序的输入是s1,...,sn，目标是按非递减顺序将数据排序。在插入排序的第i次迭代后,序列的前一部分s1,...,si会被重新安排使得它有序。插入排序接下来将si+1插入s

5、1,...,si，使得s1,...,si,si+1也是有序的。时空分析在插入排序算法中，for循环执行n-1次，但是对于一个特定的i值，while循环执行的次数依赖于输入。例如，如果输入的序列已经按非递减顺序排列，val

6、机算法（randomizedalgorithm）并不要求每一步的执行中间结果被惟一决定且只依赖于输入和前面步骤的执行结果。根据定义，当执行一个随机算法时，在某些点上，算法做出随机选择。随机算法（二）rand(i,j)：返回在整数i和j之间的（包含i和j）一个随机整数。算法的分析一个计算机程序，即便是正确的，也可能是不可用的，因为执行这个程序需要的时间或者存储这个程序的数据、变量等需要的空间太大了。例：列举一个N元集合的所有子集（编程实现）确定一个计算机程序性能估计执行一个算法需要的精确时间是很困难的

7、用程序输入的规模作为估算参数而不是直接利用程序的输入。例如，若输入是一个包含n个元素的集合，称输入的规模是n。在所有输入规模为n时执行算法需要的最少时间称为输入规模为n时的最好情形执行时间。在输入规模为n时执行算法需要的最大时间称为输入规模为n时的最坏情形执行时间。平均时间。令f和g是定义域为{1,2,3,...}上的函数若存在C1，对所有有限的正整数n满足：

8、f(n)

9、C1

10、g(n)

11、，则称f(n)最大以g(n)为阶，f(n)=O(g(n))若存在C2对所有有限的正整数n满足：

12、f(n)

13、C2

14、

15、g(n)

16、，则称f(n)最小以g(n)为阶，f(n)=(g(n))数学定义除了常数因子和有限数之外，f的上界是g，写成f(n)=O(g(n))。也称g是f的一个渐近上界。除了常数因子和有限数之外，f的下界是g，写成f(n)=(g(n))。也称g是f的一个渐近下界。除了常数因子和有限数之外，f的上下界均为g，写成f(n)=(g(n))。也称g是f的一个渐近紧密界。数学定义（二）数学定义（三）如果f(n)=O(g(n))，可得出结论除了对某些常量因子和有限数之外，