東北大學數(shù)據(jù)結構期末復習東北大學數(shù)據(jù)結構期末復習1期末復習期末復習2題型選擇題(10分)·填空題(10分)·算法應用題(算法填空,簡單問題回答)(3-4個題,35-40分)算法設計(按照已知條件設計算法或為算法補充完整)(3個題,45-50分)題型3第1章算法的性質及其與程序的區(qū)別·算法復雜性分析漸進意義下的四種記號簡單的程序段的復雜度分析第1章4算法的五個重要特征粉入有零個或多個由外部提供的量作為算法的輸入粉出算法產生至少一個量作為輸出.磅定性組成算法的每條指令是清晰的,無歧義的有限性在執(zhí)行了有窮步驟后運算終止可行性運算都是基本運算,原理上能在有限時間內完成。算法的五個重要特征5漸進意義下的記號:O,s,日,Of(N)和g(N是定義在正整數(shù)上的正函數(shù)定義1.1如果存在兩個正常數(shù)c和N,對于所有的N≥N,有f(M)≤Cg(N),則記作:f(N)=O(g(N)●當說一個算法具有O(g(n)的計算時間時,指的就是如果此算法用n值不變的同一類數(shù)據(jù)在某臺機器上運行時,所用的時間總是小于g(n)的一個常數(shù)倍?！駁(n)是計算時間f(n)的一個上界函數(shù),f(n)的數(shù)量級就是g(n)漸進意義下的記號:O,s,日,O6符號Ω的定義定義1.2如果存在兩個正常數(shù)C和自然數(shù)N0,使得當N≥N時有fN≥Cg(N),則稱函數(shù)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,都存在正整數(shù)N0,使得當N>N時有Ng(M<,則稱函數(shù)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)⊙指數(shù)時間算法exponentialtimealgorithm):計算時間用指數(shù)函數(shù)限界的算法O(2)<o(n!)<On算法分析10作業(yè)1-7作業(yè)1-711東北大學數(shù)據(jù)結構期末復習課件12東北大學數(shù)據(jù)結構期末復習課件13東北大學數(shù)據(jù)結構期末復習課件14東北大學數(shù)據(jù)結構期末復習課件15東北大學數(shù)據(jù)結構期末復習課件16東北大學數(shù)據(jù)結構期末復習課件17東北大學數(shù)據(jù)結構期末復習課件18東北大學數(shù)據(jù)結構期末復習課件19東北大學數(shù)據(jù)結構期末復習課件20東北大學數(shù)據(jù)結構期末復習課件21東北大學數(shù)據(jù)結構期末復習課件22東北大學數(shù)據(jù)結構期末復習課件23東北大學數(shù)據(jù)結構期末復習課件24東北大學數(shù)據(jù)結構期末復習課件25東北大學數(shù)據(jù)結構期末復習課件26東北大學數(shù)據(jù)結構期末復習課件27東北大學數(shù)據(jù)結構期末復習課件28東北大學數(shù)據(jù)結構期末復習課件29東北大學數(shù)據(jù)結構期末復習課件30東北大學數(shù)據(jù)結構期末復習課件31東北大學數(shù)據(jù)結構期末復習課件32東北大學數(shù)據(jù)結構期末復習課件33東北大學數(shù)據(jù)結構期末復習課件34東北大學數(shù)據(jù)結構期末復習課件35東北大學數(shù)據(jù)結構期末復習課件36東北大學數(shù)據(jù)結構期末復習課件37東北大學數(shù)據(jù)結構期末復習課件38東北大學數(shù)據(jù)結構期末復習課件39東北大學數(shù)據(jù)結構期末復習課件40東北大學數(shù)據(jù)結構期末復習課件41東北大學數(shù)據(jù)結構期末復習課件42東北大學數(shù)據(jù)結構期末復習課件43東北大學數(shù)據(jù)結構期末復習課件44東北大學數(shù)據(jù)結構期末復習課件45東北大學數(shù)據(jù)結構期末復習課件46東北大學數(shù)據(jù)結構期末復習課件47東北大學數(shù)據(jù)結構期末復習課件48東北大學數(shù)據(jù)結構期末復習課件49東北大學數(shù)據(jù)結構期末復習課件50東北大學數(shù)據(jù)結構期末復習課件51東北大學數(shù)據(jù)結構期末復習課件52東北大學數(shù)據(jù)結構期末復習課件53東北大學數(shù)據(jù)結構期末復習課件54東北大學數(shù)據(jù)結構期末復習課件55東北大學數(shù)據(jù)結構期末復習課件56東北大學數(shù)據(jù)結構期末復習課件57東北大學數(shù)據(jù)結構期末復習課件58東北大學數(shù)據(jù)結構期末復習課件59東北大學數(shù)據(jù)結構期末復習課件60東北大學數(shù)據(jù)結構期末復習課件61東北大學數(shù)據(jù)結構期末復習課件62東北大學數(shù)據(jù)結構期末復習課件63東北大學數(shù)據(jù)結構期末復習課件64東北大學數(shù)據(jù)結構期末復習課件65東北大學數(shù)據(jù)結構期末復習課件66東北大學數(shù)據(jù)結構期末復習課件67東北大學數(shù)據(jù)結構期末復習課件68東北大學數(shù)據(jù)結構期末復習課件69東北大學數(shù)據(jù)結構期末復習課件70東北大學數(shù)據(jù)結構期末復習課件71東北大學數(shù)據(jù)結構期末復習課件72東北大學數(shù)據(jù)結構期末復習課件73東北大學數(shù)據(jù)結構期末復習課件74東北大學數(shù)據(jù)結構期末復習課件75東北大學數(shù)據(jù)結構期末復習課件76東北大學數(shù)據(jù)結構期末復習課件77東北大學數(shù)據(jù)結構期末復習課件78東北大學數(shù)據(jù)結構期末復習課件79東北大學數(shù)據(jù)結構期末復習課件80東北大學數(shù)據(jù)結構期末復習課件81東北大學數(shù)據(jù)結構期末復習課件82東北大學數(shù)據(jù)結構期末復習課件83東北大學數(shù)據(jù)結構期末復習課件84東北大學數(shù)據(jù)結構期末復習課件85東北大學數(shù)據(jù)結構期末復習課件86東北大學數(shù)據(jù)結構期末復習課件87東北大學數(shù)據(jù)結構期末復習課件88東北大學數(shù)據(jù)結構期末復習課件89東北大學數(shù)據(jù)結構期末復習課件90東北大學數(shù)據(jù)結構期末復習課件91東北大學數(shù)據(jù)結構期末復習課件92東北大學數(shù)據(jù)結構期末復習課件93東北大學數(shù)據(jù)結構期末復習課件94東北大學數(shù)據(jù)結構期末復習課件95東北大學數(shù)據(jù)結構期末復習課件96東北大學數(shù)據(jù)結構期末復習課件97東北大學數(shù)據(jù)結構期末復習課件98東北大學數(shù)據(jù)結構期末復習課件99東北大學數(shù)據(jù)結構期末復習課件100東北大學數(shù)據(jù)結構期末復習課件101東北大學數(shù)據(jù)結構期末復習課件102東北大學數(shù)據(jù)結構期末復習課件103東北大學數(shù)據(jù)結構期末復習課件104東北大學數(shù)據(jù)結構期末復習課件105東北大學數(shù)據(jù)結構期末復習課件106東北大學數(shù)據(jù)結構期末復習課件107東北大學數(shù)據(jù)結構期末復習課件108東北大學數(shù)據(jù)結構期末復習課件109東北大學數(shù)據(jù)結構期末復習課件110東北大學數(shù)據(jù)結構期末復習課件111東北大學數(shù)據(jù)結構期末復習課件112東北大學數(shù)據(jù)結構期末復習課件113東北大學數(shù)據(jù)結構期末復習課件114東北大學數(shù)據(jù)結構期末復習課件115東北大學數(shù)據(jù)結構期末復習課件116東北大學數(shù)據(jù)結構期末復習課件117東北大學數(shù)據(jù)結構期末復習課件118東北大學數(shù)據(jù)結構期末復習課件119東北大學數(shù)據(jù)結構期末復習課件120東北大學數(shù)據(jù)結構期末復習課件121東北大學數(shù)據(jù)結構期末復習課件122東北大學數(shù)據(jù)結構期末復習課件123東北大學數(shù)據(jù)結構期末復習課件124東北大學數(shù)據(jù)結構期末復習課件125東北大學數(shù)據(jù)結構期末復習課件126東北大學數(shù)據(jù)結構期末復習課件127東北大學數(shù)據(jù)結構期末復習課件128東北大學數(shù)據(jù)結構期末復習課件129東北大學數(shù)據(jù)結構期末復習課件130東北大學數(shù)據(jù)結構期末復習課件131東北大學數(shù)據(jù)結構期末復習課件132東北大學數(shù)據(jù)結構期末復習課件133東北大學數(shù)據(jù)結構期末復習課件134東北大學數(shù)據(jù)結構期末復習課件13551、天下之事常成于困約，而敗于奢靡。——陸游

52、生命不等于是呼吸，生命是活動?！R梭

53、偉大的事業(yè)，需要決心，能力，組織和責任感?！撞飞?/p>

54、唯書籍不朽。——喬特

55、為中華之崛起而讀書?！芏鱽碇x謝！51、天下之事常成于困約，而敗于奢靡。——陸游

52、136東北大學數(shù)據(jù)結構期末復習東北大學數(shù)據(jù)結構期末復習137期末復習期末復習138題型選擇題(10分)·填空題(10分)·算法應用題(算法填空,簡單問題回答)(3-4個題,35-40分)算法設計(按照已知條件設計算法或為算法補充完整)(3個題,45-50分)題型139第1章算法的性質及其與程序的區(qū)別·算法復雜性分析漸進意義下的四種記號簡單的程序段的復雜度分析第1章140算法的五個重要特征粉入有零個或多個由外部提供的量作為算法的輸入粉出算法產生至少一個量作為輸出.磅定性組成算法的每條指令是清晰的,無歧義的有限性在執(zhí)行了有窮步驟后運算終止可行性運算都是基本運算,原理上能在有限時間內完成。算法的五個重要特征141漸進意義下的記號:O,s,日,Of(N)和g(N是定義在正整數(shù)上的正函數(shù)定義1.1如果存在兩個正常數(shù)c和N,對于所有的N≥N,有f(M)≤Cg(N),則記作:f(N)=O(g(N)●當說一個算法具有O(g(n)的計算時間時,指的就是如果此算法用n值不變的同一類數(shù)據(jù)在某臺機器上運行時,所用的時間總是小于g(n)的一個常數(shù)倍。●g(n)是計算時間f(n)的一個上界函數(shù),f(n)的數(shù)量級就是g(n)漸進意義下的記號:O,s,日,O142符號Ω的定義定義1.2如果存在兩個正常數(shù)C和自然數(shù)N0,使得當N≥N時有fN≥Cg(N),則稱函數(shù)f(N)當N充分大時下有界;且g(N)是它的一個下界,記為f(N)=(g(N)。這時我們說(N)的階不低于g(N)的階符號Ω的定義1430,O的定義定義f(N)=0(g(N)當且僅當f(N)=O(g(N)且f(1N=(g(N)。這時,我們說(N與g(N同階如果對于任意給定的>0,都存在正整數(shù)N0,使得當N>N時有Ng(M<,則稱函數(shù)f(M當N充分大時的階比g(M低,記為f(N)=0(g(N)例如:4NogN7=03N2+4NogN+70,O的定義144ginycg(n)f(n)f(n)cg(用f18fin)=e((m))f(a)=og(r)fun)=Q(g()(3)giny145算法分析◎多項式時間算法(polynomialtimealgorithm):可用多項式來對其計算時間限界的算法o(1<o(ogn)<o(n)<O(nlogn)<o(n2)<o(n3)⊙指數(shù)時間算法exponentialtimealgorithm):計算時間用指數(shù)函數(shù)限界的算法O(2)<o(n!)<On算法分析146作業(yè)1-7作業(yè)1-7147東北大學數(shù)據(jù)結構期末復習課件148東北大學數(shù)據(jù)結構期末復習課件149東北大學數(shù)據(jù)結構期末復習課件150東北大學數(shù)據(jù)結構期末復習課件151東北大學數(shù)據(jù)結構期末復習課件152東北大學數(shù)據(jù)結構期末復習課件153東北大學數(shù)據(jù)結構期末復習課件154東北大學數(shù)據(jù)結構期末復習課件155東北大學數(shù)據(jù)結構期末復習課件156東北大學數(shù)據(jù)結構期末復習課件157東北大學數(shù)據(jù)結構期末復習課件158東北大學數(shù)據(jù)結構期末復習課件159東北大學數(shù)據(jù)結構期末復習課件160東北大學數(shù)據(jù)結構期末復習課件161東北大學數(shù)據(jù)結構期末復習課件162東北大學數(shù)據(jù)結構期末復習課件163東北大學數(shù)據(jù)結構期末復習課件164東北大學數(shù)據(jù)結構期末復習課件165東北大學數(shù)據(jù)結構期末復習課件166東北大學數(shù)據(jù)結構期末復習課件167東北大學數(shù)據(jù)結構期末復習課件168東北大學數(shù)據(jù)結構期末復習課件169東北大學數(shù)據(jù)結構期末復習課件170東北大學數(shù)據(jù)結構期末復習課件171東北大學數(shù)據(jù)結構期末復習課件172東北大學數(shù)據(jù)結構期末復習課件173東北大學數(shù)據(jù)結構期末復習課件174東北大學數(shù)據(jù)結構期末復習課件175東北大學數(shù)據(jù)結構期末復習課件176東北大學數(shù)據(jù)結構期末復習課件177東北大學數(shù)據(jù)結構期末復習課件178東北大學數(shù)據(jù)結構期末復習課件179東北大學數(shù)據(jù)結構期末復習課件180東北大學數(shù)據(jù)結構期末復習課件181東北大學數(shù)據(jù)結構期末復習課件182東北大學數(shù)據(jù)結構期末復習課件183東北大學數(shù)據(jù)結構期末復習課件184東北大學數(shù)據(jù)結構期末復習課件185東北大學數(shù)據(jù)結構期末復習課件186東北大學數(shù)據(jù)結構期末復習課件187東北大學數(shù)據(jù)結構期末復習課件188東北大學數(shù)據(jù)結構期末復習課件189東北大學數(shù)據(jù)結構期末復習課件190東北大學數(shù)據(jù)結構期末復習課件191東北大學數(shù)據(jù)結構期末復習課件192東北大學數(shù)據(jù)結構期末復習課件193東北大學數(shù)據(jù)結構期末復習課件194東北大學數(shù)據(jù)結構期末復習課件195東北大學數(shù)據(jù)結構期末復習課件196東北大學數(shù)據(jù)結構期末復習課件197東北大學數(shù)據(jù)結構期末復習課件198東北大學數(shù)據(jù)結構期末復習課件199東北大學數(shù)據(jù)結構期末復習課件200東北大學數(shù)據(jù)結構期末復習課件201東北大學數(shù)據(jù)結構期末復習課件202東北大學數(shù)據(jù)結構期末復習課件203東北大學數(shù)據(jù)結構期末復習課件204東北大學數(shù)據(jù)結構期末復習課件205東北大學數(shù)據(jù)結構期末復習課件206東北大學數(shù)據(jù)結構期末復習課件207東北大學數(shù)據(jù)結構期末復習課件208東北大學數(shù)據(jù)結構期末復習課件209東北大學數(shù)據(jù)結構期末復習課件210東北大學數(shù)據(jù)結構期末復習課件211東北大學數(shù)據(jù)結構期末復習課件212東北大學數(shù)據(jù)結構期末復習課件213東北大學數(shù)據(jù)結構期末復習課件214東北大學數(shù)據(jù)結構期末復習課件215東北大學數(shù)據(jù)結構期末復習課件216東北大學數(shù)據(jù)結構期末復習課件217東北大學數(shù)據(jù)結構期末復習課件218東北大學數(shù)據(jù)結構期末復習課件219東北大學數(shù)據(jù)結構期末復習課件220東北大學數(shù)據(jù)結構期末復習課件221東北大學數(shù)據(jù)結構期末復習課件222東北大學數(shù)據(jù)結構期末復習課件223東北大學數(shù)據(jù)結構期末復習課件224東北大學數(shù)據(jù)結構期末復習課件225東北大學數(shù)據(jù)結構期末復習課件226東北大學數(shù)據(jù)結構期末復習課件227東北大學數(shù)據(jù)結構期末復習課件228東北大學數(shù)據(jù)結構期末復習課件229東北大學數(shù)據(jù)結構期末復習課件230東北大學數(shù)據(jù)結構期末復習課件231東北大學數(shù)據(jù)結構期末復習課件232東北大學數(shù)據(jù)結構期末復習課件233東北大學數(shù)據(jù)結構期末復習課件234東北大學數(shù)據(jù)結構期末復習課件235東北大學數(shù)據(jù)結構期末復習課件236東北大學數(shù)據(jù)結構期末復習課件237東北大學數(shù)據(jù)結構期末復習課件238東北大學數(shù)據(jù)結構期末復習課件239東北大學數(shù)據(jù)結構期末復習課件240東北大學數(shù)據(jù)結構期末復習課件241東北大學數(shù)據(jù)結構期末復習課件242東北大學數(shù)據(jù)結構期末復習