算法分析理论Theory of Alorithm Analysis.ppt

* * * * * * * * * * * * * * * William George Horner (1786 – September 22, 1837) was a British mathematician who was born in Bristol England and died in Bath England. He invented the zoetrope in 1834 * * * * * Bogus: Counterfeit or fake; not genuine: bogus money; bogus tasks. * * * * * * * * * * * * * * * * * * * * * * * * * * 渐近分析例题 续 续 续 续 顺序查找最好情形时间复杂度为Θ(1) 顺序查找最坏情形时间复杂度为Θ(n) 顺序查找平均情形时间复杂度为Θ(n) 插入排序,选择排序和rank排序最坏情形时间复杂度为O(n2).(upper bound) 更准确地讲它们的最坏情形复杂度是Θ(n2).(tight bound) 平均情形时间复杂度为Θ(n2). 多项式时间算法 如果一算法的最坏情形时间复杂度t(n)=O(nk),则称该算法为多项式复杂度的算法或有多项式界的算法. 如果一算法的最坏情形时间复杂度t(n)不能用多项式限界,则称该算法为指数复杂度的算法。这类算法可认为计算上不可行的算法。 NP-hard 问题 如果一个问题有多项式界的算法称该问题属于多项式类P 有很多实际上有意义的问题找不到有多项式界的算法称这些问题是NP-hard问题,即问题本身难. 上述难问题只能通过近似算法或启发式算法求解. 数值比较:1G指令/秒的计算能力 * * * * * * * * Dictionary/thesaurus ： The general English dictionarys main source is Houghton Mifflins premier dictionary, the American Heritage? Dictionary of the English Language, Fourth Edition. This authoritative work, the largest of the American Heritage? dictionaries, contains over 200,000 boldface forms, and more than 33,000 written examples. The Fourth Edition incorporates more than 10,000 new words and senses. * Knuth (1968, 1973) has given a list of five properties that are widely accepted as requirements for an algorithm: * 李开复 * * “←”表示”赋值“(assignment). 忽略数据类型、变量的说明等与算法无关的部分. 允许使用自然语言表示的一些 “macros”. 伪代码突出了程序使用的算法. * * * * * 注:上述分析是从程序调用的角度看,存放无序表的数组占用的空间记在上层程序的帐上. * * 返回地址（2bytes） 形参变量a地址（2bytes） 形参变量n （2bytes） * * * * * 例题2.13 [Sequential Search] 当仅考虑成功查找时，average case : t(n)=（n+1）/2； Best case: t(n)=1 , Worst case : t(n)=n 例题2.14 [Insertion into Sorted Array] Program 2.10 Inserting into a sorted list best case : 1 , worst case : n , average case: (n/2)+n/(n+1) 例题2.15 [Rank Sort Revisited] Swap操作需3次简单赋值,所以Swap操作执行时间为常数. 分析swap的执行次数. 每次执行Swap至少使一个元素就位交换后a[t]的Rank值r[t]=t,其后循环到i=t时,有r[t]=t,从而跳过循环体. 算法至多做2(n-1)次交换(swap)-上界(upper bound). best case: 当a[]为sorted, t(n)=0, worst case:当输入有以下形式时:[5,3,1,2,4],算法达到最坏