东北大学数据结构期末复习ppt课件.ppt

《东北大学数据结构期末复习ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、期末复习题型选择题（10分）填空题（10分）算法应用题（算法填空，简单问题回答）（3-4个题，35-40分）算法设计（按照已知条件设计算法或为算法补充完整）（3个题，45-50分）第1章算法的性质及其与程序的区别算法复杂性分析渐进意义下的四种记号简单的程序段的复杂度分析算法的五个重要特征输入有零个或多个由外部提供的量作为算法的输入输出算法产生至少一个量作为输出.确定性组成算法的每条指令是清晰的,无歧义的.有限性在执行了有穷步骤后运算终止可行性运算都是基本运算，原理上能在有限时间内完成。渐进意义下的记号：O,Ω,θ,оf(N)和g(N)是定义在正整数上的正函数定义1.1如果存在两个正常数c和N

2、0,对于所有的N≥N0，有f(N)≤Cg(N)，则记作：f(N)=O(g(N))。N0f(N)g(N)当说一个算法具有O(g(n))的计算时间时，指的就是如果此算法用n值不变的同一类数据在某台机器上运行时，所用的时间总是小于g(n)的一个常数倍。g(n)是计算时间f(n)的一个上界函数，f(n)的数量级就是g(n)符号Ω的定义定义1.2如果存在两个正常数C和自然数N0，使得当N≥N0时有f(N)≥Cg(N)，则称函数f(N)当N充分大时下有界；且g(N)是它的一个下界，记为f(N)=Ω(g(N))。这时我们说f(N)的阶不低于g(N)的阶。θ，o的定义θ——定义f(N)=θ(g(N))当且仅

3、当f(N)=O(g(N))且f(N)=Ω(g(N))。这时，我们说f(N)与g(N)同阶o——如果对于任意给定的ε>0，都存在正整数N0，使得当N≥N0时有f(N)/g(N)<ε，则称函数f(N)当N充分大时的阶比g(N)低，记为f(N)=o(g(N))例如：4NlogN+7=o(3N2+4NlogN+7)1.2算法分析初步多项式时间算法(polynomialtimealgorithm):可用多项式来对其计算时间限界的算法O(1)

4、(2n)

5、到原问题的解答。小问题通常与原问题相似，可以递归地使用分而治之策略来解决。例2-6在[9,12,15,27,39]中分别查找27，12，1491215273901234leftrightmidmid=(left+right)/2=(0+4)/2=2mid=(3+4)/2=3912152739leftrightmid查找27成功返回3，leftrightmid912152739leftrighttemplateintB

6、inarySearch(Ta[],constT&x,intn){//在a[0]<=a[1]<=···<=a[n-1]中搜索x//如果找到，则返回所在位置，否则返回–1intleft=;intright=;while(){intmiddle=;if(x==a[middle])returnmiddle;if(x>a[middle])left=;elseright=;}return–1;//未找到x}n-10left<=right(left+right)/2middle+1middle–1当n>1时，Tw(n)=Tw([n/2])+1,T(1)=1Tw(n)=Tw([n/2])+1=Tw([n/4

7、])+1+1……=Tw(1)+1+...+1=1+k=1+logn二分搜索的时间复杂度最坏情况下的成功检索计算时间Θ(logn)最坏情况下的不成功检索计算时间Θ(logn)最好情况下的成功检索计算时间Θ(1)最好情况下的不成功检索计算时间Θ(logn)每种不成功的检索时间都为Θ(logn)2.2二分搜索技术作业：P34，2-2中第二个和第五个算法的正确性，错误的说明原因或者给出反例2.P35,2-32-3：二