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

东北大学数据结构期末复习东北大学数据结构期末复习1期末复习期末复习2题型选择题(10分)·填空题(10分)·算法应用题(算法填空,简单问题回答)(3-4个题,35-40分)算法设计(按照已知条件设计算法或为算法补充完整)(3个题,45-50分)题型3第1章算法的性质及其与程序的区别·算法复杂性分析渐进意义下的四种记号简单的程序段的复杂度分析第1章4算法的五个重要特征粉入有零个或多个由外部提供的量作为算法的输入粉出算法产生至少一个量作为输出.磅定性组成算法的每条指令是清晰的,无歧义的有限性在执行了有穷步骤后运算终止可行性运算都是基本运算,原理上能在有限时间内完成。算法的五个重要特征5渐进意义下的记号:O,s,日,Of(N)和g(N是定义在正整数上的正函数定义1.1如果存在两个正常数c和N,对于所有的N≥N,有f(M)≤Cg(N),则记作:f(N)=O(g(N)●当说一个算法具有O(g(n)的计算时间时,指的就是如果此算法用n值不变的同一类数据在某台机器上运行时,所用的时间总是小于g(n)的一个常数倍。●g(n)是计算时间f(n)的一个上界函数,f(n)的数量级就是g(n)渐进意义下的记号:O,s,日,O6符号Ω的定义定义1.2如果存在两个正常数C和自然数N0,使得当N≥N时有fN≥Cg(N),则称函数f(N)当N充分大时下有界;且g(N)是它的一个下界,记为f(N)=(g(N)。这时我们说(N)的阶不低于g(N)的阶符号Ω的定义70,O的定义定义f(N)=0(g(N)当且仅当f(N)=O(g(N)且f(1N=(g(N)。这时,我们说(N与g(N同阶如果对于任意给定的>0,都存在正整数N0,使得当N>N时有Ng(M<,则称函数f(M当N充分大时的阶比g(M低,记为f(N)=0(g(N)例如:4NogN7=03N2+4NogN+70,O的定义8ginycg(n)f(n)f(n)cg(用f18fin)=e((m))f(a)=og(r)fun)=Q(g()(3)giny9算法分析◎多项式时间算法(polynomialtimealgorithm):可用多项式来对其计算时间限界的算法o(1<o(ogn)<o(n)<O(nlogn)<o(n2)<o(n3)⊙指数时间算法exponentialtimealgorithm):计算时间用指数函数限界的算法O(2)<o(n!)<On算法分析10作业1-7作业1-711东北大学数据结构期末复习课件12东北大学数据结构期末复习课件13东北大学数据结构期末复习课件14东北大学数据结构期末复习课件15东北大学数据结构期末复习课件16东北大学数据结构期末复习课件17东北大学数据结构期末复习课件18东北大学数据结构期末复习课件19东北大学数据结构期末复习课件20东北大学数据结构期末复习课件21东北大学数据结构期末复习课件22东北大学数据结构期末复习课件23东北大学数据结构期末复习课件24东北大学数据结构期末复习课件25东北大学数据结构期末复习课件26东北大学数据结构期末复习课件27东北大学数据结构期末复习课件28东北大学数据结构期末复习课件29东北大学数据结构期末复习课件30东北大学数据结构期末复习课件31东北大学数据结构期末复习课件32东北大学数据结构期末复习课件33东北大学数据结构期末复习课件34东北大学数据结构期末复习课件35东北大学数据结构期末复习课件36东北大学数据结构期末复习课件37东北大学数据结构期末复习课件38东北大学数据结构期末复习课件39东北大学数据结构期末复习课件40东北大学数据结构期末复习课件41东北大学数据结构期末复习课件42东北大学数据结构期末复习课件43东北大学数据结构期末复习课件44东北大学数据结构期末复习课件45东北大学数据结构期末复习课件46东北大学数据结构期末复习课件47东北大学数据结构期末复习课件48东北大学数据结构期末复习课件49东北大学数据结构期末复习课件50东北大学数据结构期末复习课件51东北大学数据结构期末复习课件52东北大学数据结构期末复习课件53东北大学数据结构期末复习课件54东北大学数据结构期末复习课件55东北大学数据结构期末复习课件56东北大学数据结构期末复习课件57东北大学数据结构期末复习课件58东北大学数据结构期末复习课件59东北大学数据结构期末复习课件60东北大学数据结构期末复习课件61东北大学数据结构期末复习课件62东北大学数据结构期末复习课件63东北大学数据结构期末复习课件64东北大学数据结构期末复习课件65东北大学数据结构期末复习课件66东北大学数据结构期末复习课件67东北大学数据结构期末复习课件68东北大学数据结构期末复习课件69东北大学数据结构期末复习课件70东北大学数据结构期末复习课件71东北大学数据结构期末复习课件72东北大学数据结构期末复习课件73东北大学数据结构期末复习课件74东北大学数据结构期末复习课件75东北大学数据结构期末复习课件76东北大学数据结构期末复习课件77东北大学数据结构期末复习课件78东北大学数据结构期末复习课件79东北大学数据结构期末复习课件80东北大学数据结构期末复习课件81东北大学数据结构期末复习课件82东北大学数据结构期末复习课件83东北大学数据结构期末复习课件84东北大学数据结构期末复习课件85东北大学数据结构期末复习课件86东北大学数据结构期末复习课件87东北大学数据结构期末复习课件88东北大学数据结构期末复习课件89东北大学数据结构期末复习课件90东北大学数据结构期末复习课件91东北大学数据结构期末复习课件92东北大学数据结构期末复习课件93东北大学数据结构期末复习课件94东北大学数据结构期末复习课件95东北大学数据结构期末复习课件96东北大学数据结构期末复习课件97东北大学数据结构期末复习课件98东北大学数据结构期末复习课件99东北大学数据结构期末复习课件100东北大学数据结构期末复习课件101东北大学数据结构期末复习课件102东北大学数据结构期末复习课件103东北大学数据结构期末复习课件104东北大学数据结构期末复习课件105东北大学数据结构期末复习课件106东北大学数据结构期末复习课件107东北大学数据结构期末复习课件108东北大学数据结构期末复习课件109东北大学数据结构期末复习课件110东北大学数据结构期末复习课件111东北大学数据结构期末复习课件112东北大学数据结构期末复习课件113东北大学数据结构期末复习课件114东北大学数据结构期末复习课件115东北大学数据结构期末复习课件116东北大学数据结构期末复习课件117东北大学数据结构期末复习课件118东北大学数据结构期末复习课件119东北大学数据结构期末复习课件120东北大学数据结构期末复习课件121东北大学数据结构期末复习课件122东北大学数据结构期末复习课件123东北大学数据结构期末复习课件124东北大学数据结构期末复习课件125东北大学数据结构期末复习课件126东北大学数据结构期末复习课件127东北大学数据结构期末复习课件128东北大学数据结构期末复习课件129东北大学数据结构期末复习课件130东北大学数据结构期末复习课件131东北大学数据结构期末复习课件132东北大学数据结构期末复习课件133东北大学数据结构期末复习课件134东北大学数据结构期末复习课件13551、天下