《算法分析与设计所研究的主要内容.ppt》由会员分享，可在线阅读，更多相关《算法分析与设计所研究的主要内容.ppt（18页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、算法设计与分析算法设计与分析一、问题的提出查找问题：给定一个数组A，其长度为n，所存放的元素为(互不相同且已按从小到大的顺序排列的)n个整数。对于给定的正整数k，问k在不在数组中？若在则返回元素在数组中的下标；否则返回-1。试给出解决问题的算法。应用：IP电话卡的用户认证1、顺序查找算法：P362、有序数组的顺序查找：P543、有序数组的二分查找算法：P56 算法的C语言实现：search.txt三个不同的算法1、正确吗？2、可实际应用吗？3、谁优、谁劣？4、查找问题是否还有更好的算法？二、算法设计的5大要素1、正确性、正确性2、工作量，即时间开销、工作量，即时间开销3、空间占用量，即内存空间
2、的开销空间占用量，即内存空间的开销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 relat
3、ionships 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-P
4、30 四、工作量 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)|iDn 称 W(n)为最坏情况
5、下的复杂性。最好情况：最好情况：称使复杂性取最小的那个输入为最好情况。min t(I)|iDn平均情况：平均情况：称A(n)=iDn 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+lgn-1