资源描述
,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,算法设计与分析,一、问题的提出,查找问题：,给定一个数组,A，,其长度为,n，,所存放的元素为(互不相同且已按从小到大的顺序排列的),n,个整数。对于给定的正整数,k，,问,k,在不在数组中？若在则返回元素在数组中的下标；否则返回-1,。,试给出解决问题的算法。,应用：,IP,电话卡的用户认证,1、顺序查找算法：,P36,2、有序数组的顺序查找：,P54,3、有序数组的二分查找算法：,P56,算法的,C,语言实现：,search.txt,三个不同的算法,1、正确吗？,2、,可实际应用吗？,3、,谁优、谁劣？,4、查找问题是否还有更好的算法？,二、算法设计的5大要素,1、正确性,2、工作量，即时间开销,3、,空间占用量，即内存空间的开销,4、,简单、明白,5、,最优性,三、正确性,1、 If the preconditions (,inputs the algorithm or statement is expected to work on,)are satisfied, the,postconditions,(,result the algorithm or statement is to produce for each input,) will be true when the algorithm terminates.,try to prove statements about the relationships between the input and the output.,算法正确性的两个方面,1、 the solution method.,一系列的,与算法工作对象相关的,引理和定理来说明这种方法和一个公式的正确性。,Once the method is established, it is implemented in a program.,2、the sequence of instruction for carrying the algorithm out,that is ,its implementation.,证明一个大而复杂的程序的正确性，需要把它分解为若干小的模块。,数理逻辑：,P28-P30,四、工作量,Let,Dn,be the set of,imputs,of size n for the problem under consideration, I be an element of inputs, t(I) be the number of basic operations performed by the algorithm on input I.,算法复杂性的量化及评判标准算法复杂性的量化及评判标准.,ppt,最坏情况、最好情况、平均情况,最坏情况：,称使复杂性最大的那个输入为最坏情况。,W(n)=max t(I)|i,Dn,称,W(n),为最坏情况下的复杂性。,最好情况：,称使复杂性取最小的那个输入为最好情况。,min t(I)|i,Dn,平均情况：,称,A(n)=,i,Dn,Pr(I)t(I),为平均情况下的复杂性,复杂性计算,顺序查找算法(,P36):,求：算法在最好、最坏、平均情况下的复杂性,平均情况下：,C,在数组中的平均情况,C,不在数组中,平均情况(在数组中的概率为,q),有序数组的查找问题,P54,求平均情况下的复杂性,五、最优性,1、决策树,例 给定一个含8个元素的数组，画出任意2个通过比较进行查找的算法（顺序、二分、黄金分割）所对应的决策树。,二分查找算法的最优性,二分查找算法对应一个完全或近似满的二叉决策树。,定理1.16：,通过比较在一个含,n,个元素的数组中进行查找的算法最坏情况下至少要做,lg,(n+1),二分搜索法.,doc,（P56）,2、求最大元问题的下界,P40,对论,下界为,n-1,求次大元以及问题的下界,锦标赛法.,doc,次大元只能在输给冠军的那些元素中取,下界为,n-1+,lg,n,-1,
展开阅读全文