算法設(shè)計與分析 課件 許瑾晨 0 算法導(dǎo)論-第三章 遞歸

信息工程大學(xué)算法設(shè)計與分析算法導(dǎo)論國家級實驗教學(xué)示范中心計算機學(xué)科組規(guī)劃教材算法設(shè)計與分析Python案例詳解微課視頻版問題1：從課程名可以得到的課程信息有什么？算法設(shè)計算法分析問題2：可以從哪些方面評價一個應(yīng)用程序的好壞？安全性用戶體驗正確性性能……問題3：算法有“好壞”之分嗎？算法有政治立場嗎？這是一門重要的，和工作生活息息相關(guān)的課程，是一門關(guān)注于性能的課程，即要能設(shè)計好的算法，也要能分析算法的性能。1.課程定位計算機相關(guān)專業(yè)的核心課程對培養(yǎng)計算思維和求解問題能力起到重要作用為學(xué)習(xí)其它專業(yè)課奠定扎實的基礎(chǔ)以算法分析方法和常用的算法設(shè)計策略的學(xué)習(xí)為主2.課程目標(biāo)從算法角度運用數(shù)學(xué)工具分析問題和解決問題的基本能力；①能夠正確地分析并評價算法，進一步設(shè)計出高效算法；配合實踐教學(xué)，理論聯(lián)系實際，理論指導(dǎo)實踐，規(guī)范完成作業(yè)，鞏固所學(xué)知識；②③能力素質(zhì)3.課程教材規(guī)劃教材理論實踐結(jié)合配有微課視頻課程思政典型應(yīng)用詳解代碼可直接運行注：國家級實驗教學(xué)示范中心計算機專業(yè)組規(guī)劃教材；教育部高等學(xué)校計算機專業(yè)教學(xué)指導(dǎo)委員會推薦教材。4.網(wǎng)絡(luò)助學(xué)資源2中國大學(xué)MOOC國家精品課程《算法設(shè)計與分析》1《算法設(shè)計與分析》微課4.網(wǎng)絡(luò)助學(xué)資源2中國大學(xué)MOOC國家精品課程《算法設(shè)計與分析》3麻省理工學(xué)院公開課《算法導(dǎo)論》CharlesLeiserson&ErikDemaine1《算法設(shè)計與分析》微課4.網(wǎng)絡(luò)助學(xué)資源2中國大學(xué)MOOC國家精品課程《算法設(shè)計與分析》3麻省理工學(xué)院公開課《算法導(dǎo)論》4國內(nèi)外知名的在線評測系統(tǒng)：POJ、洛谷等1《算法設(shè)計與分析》微課最終成績=平時成績(30%)+期末筆試(70%)平時成績=課前預(yù)習(xí)（5%）+課堂測試

(5%)+編程實踐

(20%)5.考核評價加入平時成績的構(gòu)成圖示■

課前預(yù)習(xí)5%20%■

編程實踐■

課堂測試5%總學(xué)時40，理論30+實踐10test.ctest_2.ctest_3.c總學(xué)時40，理論30+實踐10算法分析□算法分析準(zhǔn)則□時間復(fù)雜度分析方法□最優(yōu)性定義與證明□NP完全性理論算法設(shè)計□遞歸與分治□動態(tài)規(guī)劃□貪心法□回溯法□分支限界法□概率算法實踐環(huán)節(jié)：算法設(shè)計策略的編程實踐2.課程重點難點1.每種算法設(shè)計策略的適用條件、求解步驟、分析方法和典型應(yīng)用的求解方法等。算法設(shè)計策略典型應(yīng)用遞歸與分治策略二分搜索、快速排序、歸并排序、棋盤覆蓋、大整數(shù)相乘、矩陣相乘、最接近點對、…動態(tài)規(guī)劃矩陣連乘、0-1背包、最長公共子序列、最大子段和、最優(yōu)二叉搜索樹、、…貪心活動安排、單源最短路徑、哈夫曼編碼、背包問題、最小生成樹、最優(yōu)裝載、過河問題、…回溯N皇后、0-1背包、旅行售貨員、子集和、裝載問題、最大團問題、圖的m著色、連續(xù)郵資問題…分支限界0-1背包、旅行售貨員、電路板排列、批處理作業(yè)調(diào)度、布線問題、裝載問題、最大團問題、…分治動態(tài)規(guī)劃貪心動態(tài)規(guī)劃回溯分支限界2.不同算法設(shè)計策略之間的聯(lián)系與區(qū)別。1.指導(dǎo)策略提升抽象分析能力看懂直白題目厘清問題本質(zhì)轉(zhuǎn)變提升3種能力，完成3個轉(zhuǎn)變1.指導(dǎo)策略提升抽象分析能力看懂直白題目厘清問題本質(zhì)轉(zhuǎn)變提升3種能力，完成3個轉(zhuǎn)變問題：一般而言，兔子在出生兩個月后，就有繁殖能力，一對兔子每個月能生出一對小兔子來。如果所有兔子都不死，那么一年以后可以繁殖多少對兔子？1.指導(dǎo)策略提升抽象分析能力看懂直白題目厘清問題本質(zhì)轉(zhuǎn)變提升3種能力，完成3個轉(zhuǎn)變問題：一般而言，兔子在出生兩個月后，就有繁殖能力，一對兔子每個月能生出一對小兔子來。如果所有兔子都不死，那么一年以后可以繁殖多少對兔子？等價為：斐波那契數(shù)列1.指導(dǎo)策略提升抽象分析能力拓展計算思維能力直觀單一思路多種算法策略轉(zhuǎn)變看懂直白題目厘清問題本質(zhì)轉(zhuǎn)變提升3種能力，完成3個轉(zhuǎn)變十個藥瓶，裝有相同數(shù)量的藥，但其中有1瓶每一片藥都輕1毫克，給你一把秤，你需要用幾次秤，才能找到藥片輕一點的藥瓶？只能使用1次秤，你還能找到嗎？有問題的藥不確定有哪幾瓶，依然只能使用1次秤，你能一次全找到嗎？1.指導(dǎo)策略轉(zhuǎn)變只求可行方法擇優(yōu)選擇方法提升抽象分析能力拓展計算思維能力增強算法評價能力直觀單一思路多種算法策略轉(zhuǎn)變看懂直白題目厘清問題本質(zhì)轉(zhuǎn)變提升3種能力，完成3個轉(zhuǎn)變2.具體做法---上下結(jié)合，內(nèi)外延伸自主學(xué)習(xí)（課下xh）要點講解（課上60m）隨堂研討（課上25m）隨堂測試（課上5m）編程實踐（課下xh）提前給出學(xué)習(xí)內(nèi)容，課前反饋學(xué)習(xí)情況（集中反饋）：課前1天隨堂測試主要對自主學(xué)習(xí)內(nèi)容掌握情況進行評估，成績計入平時成績編程實踐主要完成課后作業(yè)及課堂實踐針對實踐題目組織研討交流編程實現(xiàn)完成解題報告2.具體做法---怎么練在線評測系統(tǒng)和本地編程相結(jié)合569112471013812131415數(shù)字華容道：用盡量少的步數(shù)，盡量短的時間，將棋盤上的數(shù)字方塊，按照從左到右、從上到下的順序重新排列整齊。解題過程使用的方法是什么？設(shè)有n個城市，已知任意兩城市間距離不等，現(xiàn)有一情報員想從鄭州出發(fā)巡回經(jīng)過每一城市（且每城市只經(jīng)過一次），最后又回到出發(fā)點，問如何找一條最短路徑。1.(2分)關(guān)于算法特征描述正確的有？A：

確定性B：

可行性C：

無窮性D：

有輸入E：

有輸出F: 有窮性2.(2分)分析算法的指標(biāo)有哪些？A：

正確性B：

最優(yōu)性C：

簡單性D：

時間復(fù)雜度E：

空間復(fù)雜度F: 有窮性3.(1分)判斷：算法就是程序。A：

正確B：

錯誤4.(1分)判斷：算法可以沒有輸入，但必須有輸出。A：

正確B：

錯誤信息工程大學(xué)算法設(shè)計與分析算法分析國家級實驗教學(xué)示范中心計算機學(xué)科組規(guī)劃教材算法設(shè)計與分析Python案例詳解微課視頻版一二三算法基礎(chǔ)算法分析準(zhǔn)則正確性、簡單性、最優(yōu)性時間復(fù)雜度、空間復(fù)雜度NP完全理論P、NP、NPC問題基本概率和特征算法與程序重點掌握：1.算法的時間復(fù)雜度分析方法2.P、NP、NPC問題的相互關(guān)系信息工程大學(xué)算法設(shè)計與分析算法分析國家級實驗教學(xué)示范中心計算機學(xué)科組規(guī)劃教材算法設(shè)計與分析Python案例詳解微課視頻版一二三算法基礎(chǔ)算法分析準(zhǔn)則正確性、簡單性、最優(yōu)性時間復(fù)雜度、空間復(fù)雜度NP完全理論P、NP、NPC問題基本概率和特征算法與程序重點掌握：1.算法的時間復(fù)雜度分析方法2.P、NP、NPC問題的相互關(guān)系信息工程大學(xué)算法設(shè)計與分析算法基礎(chǔ)國家級實驗教學(xué)示范中心計算機學(xué)科組規(guī)劃教材算法設(shè)計與分析Python案例詳解微課視頻版什么是算法算法具備哪些特征算法與程序的關(guān)系一二三非形式定義：一個有窮的運算規(guī)則序列運算規(guī)則確定了問題的解決方法序列給出了解決方法的先后順序有窮性表現(xiàn)在：運算規(guī)則序列是有窮的

對問題的合法輸入，算法經(jīng)有限

次運算后能終止并給出問題的解特征：確定性

－算法中的每種運算有確切的定義，

不允許存在多義性和不確定性?？尚行?/p>

－每種運算都是相當(dāng)基本的、可行

的，原則上能精確實施。有窮性

－算法執(zhí)行有窮步運算后能夠終止。有0個或1個以上的輸入有1個以上的輸出

測試選擇題：以下對算法特征描述正確的有（）

A：確定性 B：可行性 C：無窮性 D：必須有輸入 E：必須有輸出 F：有窮性 G：可以沒有輸入 H：可以沒有輸出與程序的聯(lián)系和區(qū)別：聯(lián)系：

程序＝算法＋數(shù)據(jù)結(jié)構(gòu)，算法實現(xiàn)就是 把算法變?yōu)橐粋€程序。區(qū)別：

描述語言和實現(xiàn)方式不同

算法具有有窮性判斷題：算法就是程序

A：正確 B：錯誤測試信息工程大學(xué)算法設(shè)計與分析算法分析準(zhǔn)則國家級實驗教學(xué)示范中心計算機學(xué)科組規(guī)劃教材算法設(shè)計與分析Python案例詳解微課視頻版什么是算法分析算法分析的目的算法分析準(zhǔn)則一二三算法設(shè)計設(shè)計出現(xiàn)實問題的求解方法，包括數(shù)學(xué)的方法和邏輯的方法，并用算法語言描述出來。算法分析分析算法的各種性態(tài)，確定算法的優(yōu)劣。主要有：時間復(fù)雜度、空間復(fù)雜度、正確性、簡單性、最優(yōu)性。算法分析目的就算法本身而言，確定算法的優(yōu)劣程度，進而選擇、修改、創(chuàng)造算法。就算法所解決的問題而言，確定問題實例的可計算程度。可計算程度算法不可解－不存在解決該問題的算法算法可解－解決問題的算法在理論上是存在的實際可解－存在現(xiàn)實可行、可接受的有效算法國產(chǎn)超級計算機投身國家需要的領(lǐng)域，為國家的技術(shù)強盛，貢獻自己的力量！正確性----算法設(shè)計的最低要求工作量----算法在理論層面需要的時間空間量----算法在理論層面需要的存儲簡單性----算法可被理解程度最優(yōu)性----算法在同類算法中的水平最重要的準(zhǔn)則：時間復(fù)雜度（工作量）測試選擇題：分析算法的準(zhǔn)則有（）

A：

正確性 B：

最優(yōu)性 C：

簡單性 D：

時間復(fù)雜度 E：

空間復(fù)雜度 F: 有窮性信息工程大學(xué)算法設(shè)計與分析算法分析—正確性國家級實驗教學(xué)示范中心計算機學(xué)科組規(guī)劃教材算法設(shè)計與分析Python案例詳解微課視頻版正確性對算法的任何有效（合法）輸入，算法能在有限時間內(nèi)，給出問題的正確結(jié)果。證明步驟

1.建立一個給出算法輸入后算法產(chǎn)生什么樣的結(jié)果的命題。2.證明算法中使用的各種方法是正確的。3.證明命題是正確的。正確性

1.

j=1;2.whilej≤nandL[j]≠xdo3.j=j+1;4.ifj>nthenj=0;5.

output(j)

命題1：如果L是一個具有n項的表，若表中有一個等于X的項，那么這個算法以將j置成表中等于X的項的下標(biāo)而結(jié)束；否則，若表中沒有等于X的項，則這個算法將j置成0而結(jié)束。命題2：給定一個具有n項（n≥0）的數(shù)組L，并且給定X，當(dāng)X在L之中時，順序搜索算法將j置成X在L中第一次出現(xiàn)處的下標(biāo)而結(jié)束，否則算法將j置成0而結(jié)束。正確性缺點：一是沒有說明當(dāng)x在表中多次出現(xiàn)時的結(jié)果；二是沒有指明算法在n為何值時工作。

1.

j:=1;2.whilej≤nandL[j]≠xdo3.j:=j+1;4.ifj>nthenj:=0;5.output(j)

命題3：對于1≤k≤n+1,假若算法第k次地執(zhí)行第2行中的測試，則下列條件成立：1.j=k而且對1≤i＜k,L(i)≠X。2.若k≤n而且L(k)=X，則算法將在執(zhí)行了第2行中的測試和第4行以后結(jié)束，此時j仍然等于k。3.若k=n+1，則算法將在執(zhí)行了第2行中的測試和第4行以后結(jié)束，此時j=0。數(shù)學(xué)歸納法證明的思路：1.證明k=1時，命題3成立；2.假設(shè)k<n+1時，命題3成立；3.證明k+1時，命題3成立命題3：對于1≤k≤n+1,假若算法第k次地執(zhí)行第2行中的測試，則下列條件成立：1.j=k而且對1≤i＜k,L(i)≠X。2.若k≤n而且L(k)=X，則算法將在執(zhí)行了第2行中的測試和第4行以后結(jié)束，此時j仍然等于k。3.若k=n+1，則算法將在執(zhí)行了第2行中的測試和第4行以后結(jié)束，此時j=0。證明一個算法的正確性，首先需要建立（），并常用（）進行證明。A：給出輸入后算法將要產(chǎn)生什么結(jié)果的命題B：解決問題的方法C：數(shù)學(xué)歸納法D：反證法測試正確性是如何證明的；正確性是可以證明的；對于長而復(fù)雜的（即實際的）程序來說，正確性證明確實是一件極為復(fù)雜和困難的工作。理論和實踐結(jié)合，以滿足實踐需求為目標(biāo)信息工程大學(xué)算法設(shè)計與分析算法分析—時間復(fù)雜度國家級實驗教學(xué)示范中心計算機學(xué)科組規(guī)劃教材算法設(shè)計與分析Python案例詳解微課視頻版如何度量如何表示計算步驟一二三算法……程序電腦運行環(huán)境編程語言編譯器……思考：

執(zhí)行算法的實際時間？

實現(xiàn)算法指令（語句）條數(shù)？

實現(xiàn)算法程序的循環(huán)次數(shù)？通常用：算法所使用的一種或幾種“基本操作”的執(zhí)行次數(shù)來度量?；静僮鳎鉀Q某一問題的算法中，處于基本關(guān)鍵地位，執(zhí)行次數(shù)足以反映算法效率的操作。如：搜索數(shù)組元素的“比較操作”；多項式計算中的“乘法操作”和“加法操作”?；静僮鳎罕容^運算

給變量賦值

跟蹤對象引用

函數(shù)或方法調(diào)用數(shù)組元素訪問

從函數(shù)或方法中返回算術(shù)運算（加、減、乘、除等）

測試單選題：算法的時間復(fù)雜度分析，主要針對（）； A：循環(huán) B：所有指令 C：基本操作算法的“工作量”與問題的輸入規(guī)模、具體的輸入有關(guān)。

問題的輸入有多少種？每種(類)輸入出現(xiàn)的概率及其所需要的處理時間（基本操作的執(zhí)行次數(shù)）？輸入n是多少

？算法的工作量通常有“平均時間復(fù)雜度（或平均性態(tài)）”和“最壞時間復(fù)雜度(或最壞性態(tài))”兩種表示。

Dn：輸入規(guī)模為n的輸入集合I：一個尺寸為n的輸入P(I)：輸入為I出現(xiàn)的概率t(I)：對于I,算法做的基本操作次數(shù)平均時間復(fù)雜度：最壞時間復(fù)雜度：注:實踐表明，可操作性最好、且最有實際價值的，是最壞時間復(fù)雜度。

平均時間復(fù)雜度分析步驟為： 1.確定基本操作； 2.分析不同的輸入種類并確定出現(xiàn)概率； 3.計算每種輸入執(zhí)行的基本操作次數(shù)； 4.按公式計算； 5.化簡函數(shù)。最壞時間復(fù)雜度分析步驟為： 1.確定基本操作； 2.分析輸入的最壞情況； 3.計算最壞情況輸入下執(zhí)行基本操作的次數(shù)； 4.化簡函數(shù)。測試單選題：最常使用的時間復(fù)雜度是（） A：平均時間復(fù)雜度 B：最壞時間復(fù)雜度算法設(shè)計與分析算法分析-時間復(fù)雜度-漸近分析及符號表示信息工程大學(xué)國家級實驗教學(xué)示范中心計算機學(xué)科組規(guī)劃教材算法設(shè)計與分析Python案例詳解微課視頻版計數(shù)法，即統(tǒng)計算法執(zhí)行的基本操作次數(shù)步驟： 1.確定基本操作； 2.按相關(guān)公式建立關(guān)于n的表達式； 3.化簡表達式。

什么是漸近分析漸近分析符號一二算法分析中的Bigidea漸近分析在問題規(guī)模足夠大后，時間復(fù)雜度的增長趨勢。主流（忽略細節(jié)）+長遠（規(guī)模足夠大）時間復(fù)雜度即漸近時間復(fù)雜度(AsymptoticTimeComplexity)約翰·霍普克羅夫特（JohnEdwardHopcroft）符號：O定義：設(shè)f(n)和g(n)是定義在自然數(shù)集N上的函數(shù)，若存在常數(shù)C>0和正整數(shù)n0，使得對所有的n>n0，若f(n)≤C*g(n)，則稱f(n)的階不高于g(n)的階且g(n)是f(n)的一個上界，記作f(n)=O(g(n))。即表明:f(n)的增長最多像g(n)的增長那樣快。f(n)cg(n)n0運行時間輸入規(guī)模符號：

定義：若f(n)=

(g(n))且g(n)=

(f(n))，則稱f(n)和g(n)是同階的，且記作：f(n)=

(g(n))或g(n)=

(f(n))。即，表明:f(n)的增長和g(n)的增長同樣快，稱

(g(n))是f(n)的準(zhǔn)確界。（C>0,為常數(shù)）符號：

定義：若f(n)≥Cg(n),則稱f(n)的階不低于g(n)的階，并記作f(n)=

(g(n))，即，表明:f(n)的增長至少像g(n)那樣快，稱

(g(n))是f(n)的下界。符號：o定義：如果對于任意給定的ε≥0，都存在非負(fù)整數(shù)n0，使得當(dāng)N≥n0時有f(N)<εg(N)，則稱函數(shù)f(N)當(dāng)N充分大時，比g(N)低階，記為f(N)=o(g(N))。o記為緊上界符號。符號：ω定義：若g(N)=o(f(N)),即當(dāng)N充分大時，f(N)的階比g(N)高，則記f(N)=ω(g(N))。ω記為緊下界符號。測試單選題：在時間復(fù)雜度的結(jié)果表示中，表示下界的符號為（）；表示同階的符號為（）；表示上界的符號為（）；表示緊上界的符號為（）；表示緊下界的符號為（）。A：O B：

C：

D：o E：ω函數(shù)階關(guān)系證明證明兩個函數(shù)滿足同階、低階或高階關(guān)系，有以下方法：1.按照階的定義，找到合適的常數(shù)c和n0。2.使用求極限方法，如洛必達法則。幾點說明不能寫O(g(n))=f(n)或

(g(n))=f(n)。在函數(shù)中，低階項不影響函數(shù)的階。時間復(fù)雜度表達式中選擇階最高的項，去掉系數(shù)，加上O，即可得到漸進時間復(fù)雜度。當(dāng)改進算法時，首先降低算法復(fù)雜度的階，其次再考慮減小項的系數(shù)，再減少低階項。幾個例子例1：f(n)=2022f(n)=O(1)例2：f(n)=n+2log3nf(n)=O(n)例3：f(n)=n2/5+lognf(n)=O(n2/5)例4：f(n)=2n3+900n2+nf(n)=O(n3)算法設(shè)計與分析算法分析-時間復(fù)雜度-非遞歸實現(xiàn)的分析信息工程大學(xué)國家級實驗教學(xué)示范中心計算機學(xué)科組規(guī)劃教材算法設(shè)計與分析Python案例詳解微課視頻版

例：設(shè)L是一個n項數(shù)組（n≥0），x是某一給定項，求在L中第一個與x匹配的項的數(shù)組下標(biāo)。即：若L[j]=x且對i:0≤i<j,L[i]≠x時，輸出j，否則輸出“0”，1≤j≤n。輸入：L,n,x輸出：j1.j=1;2.whilej≤nandL[j]≠xdo3.j=j+1;4.ifj>nthenj=0;5.printf(j)

順序搜索算法首先,確定基本操作:x與L中的項的比較操作

平均時間復(fù)雜度分析過程輸入分類：①x在L中的輸入，有n種，令I(lǐng)i為x＝L[i]的輸入，1≤i≤n；

②x不在L中的輸入，有1種，令I(lǐng)n+1為x≠L[i]的輸入，1≤i≤n；共有n+1種輸入基本操作次數(shù)：t(Ii)=i,1≤i≤nt(In+1)=n輸入出現(xiàn)概率：假定x在L中出現(xiàn)的概率為q且出現(xiàn)再每個位置的可能性均等，知：當(dāng)q=1/2時，A(n)=(3n+1)/4=O(n)

最壞時間復(fù)雜度分析過程最壞輸入：①x不在L中；

②x在L中的最后一項出現(xiàn)；共有兩種情況基本操作次數(shù)：t(Ii)=n,1≤i≤n+1時間復(fù)雜度：

測試選擇題：順序搜索算法的最壞情況有（）種A：1B：2C：3D：4算法設(shè)計與分析算法分析-時間復(fù)雜度-遞歸實現(xiàn)-迭代法信息工程大學(xué)國家級實驗教學(xué)示范中心計算機學(xué)科組規(guī)劃教材算法設(shè)計與分析Python案例詳解微課視頻版遞推方程求解方法--迭代法一二遞推方程：一般形式為：其中，ni為第i個子問題的規(guī)模；T(ni)為第i個子問題的時間復(fù)雜度；g(n)為把大問題劃分成若干小問題及把各個小問題的解合并成整個問題的解所需的工作量之和；Ci為常數(shù)；ni<n，1≤i≤k。求解方法：迭代法

直接迭代：插入排序最壞情況下時間分析換元迭代：二分歸并排序最壞情況下時間分析差消迭代：快速排序平均情況下的時間分析遞歸樹主定理

直接迭代算法1

InsertSort(A,n)//A為n個數(shù)的數(shù)組1.i=n-12.ifn==0return3.InsertSort(A,n-1)

4.whilei>0andA[i]<A[i-1]do5.A[i+1]

A[i]6.i

i-1W(n)=W(n

1)+n1=[W(n2)+n2]+n1=W(n2)+(n2)+(n1)

=[W(n3)+n3]+(n2)+(n1)=…=W(1)+1+2+…+(n2)+(n1)=1+2+…+(n2)+(n1)=n(n1)/2=O(n2)

換元迭代算法2

MergeSort(A,p,r)//歸并排序數(shù)組A[p..r]1.ifp<r2.thenq

(p+r)/23.MergeSort(A,p,q)4.MergeSort(A,q+1,r)5.Merge(A,p,q,r)

令差消迭代快速排序平均時間復(fù)雜度分析測試選擇題：對于遞推式

①

②

③

算法設(shè)計與分析算法分析-時間復(fù)雜度-遞歸實現(xiàn)-遞歸樹信息工程大學(xué)國家級實驗教學(xué)示范中心計算機學(xué)科組規(guī)劃教材算法設(shè)計與分析Python案例詳解微課視頻版迭代法

直接迭代換元迭代差消迭代遞歸樹主定理

遞歸樹

遞歸樹是一棵結(jié)點帶權(quán)值的樹，結(jié)點的權(quán)值表示問題劃分和合并需要的代價，結(jié)點的兒子結(jié)點對應(yīng)子問題的遞歸函數(shù)調(diào)用。T(n)自由項遞歸項g(n)….T(ni)T(ni)T(ni)遞歸樹W(n)n-1W(n/2)W(n/2)n/2-1n-1n/2-1W(n/4)W(n/4)W(n/4)W(n/4)生成過程

n-1n/2-1n/2-1n/4-1n/4-1n/4-1n/4-1n-1n-2n-4………0000……0000n-2k遞歸樹1構(gòu)造遞歸樹；2計算樹中每層結(jié)點的權(quán)值和；3計算各層權(quán)值的總和。……..Num1Num2Num3Num4Num5SUM遞歸樹T(n)=T(n/3)+T(2n/3)+n層數(shù)k:n(2/3)k=1(3/2)k=n

k=log3/2nT(n)=kn=O(nlogn)測試

算法設(shè)計與分析算法分析-時間復(fù)雜度-遞歸-主定理信息工程大學(xué)國家級實驗教學(xué)示范中心計算機學(xué)科組規(guī)劃教材算法設(shè)計與分析Python案例詳解微課視頻版迭代法

直接迭代換元迭代差消迭代遞歸樹主定理

主定理

主定理

T(n)=

(nlogba)T(n)=

(f(n))f(n)

(nlogba

lgn)n

n-

對于紅色部分，主定理無法求解。

主定理例1：求解遞推方程解：上述遞推方程中的a=9,b=3,f(n)=n，那么

相當(dāng)于主定理的第一種情況，其中

=1。根據(jù)定理得到

例2：求解遞推方程解：上述遞推方程中的a=1,b=3/2,f(n)=1，那么

相當(dāng)于主定理的第二種情況。根據(jù)定理得到

主定理

例4求解

a=b=2,，f(n)=nlogn不存在

>0使得nlogn=

(n1+

)成立，不能使用主定理。

測試算法設(shè)計與分析算法分析-時間復(fù)雜度-比較信息工程大學(xué)國家級實驗教學(xué)示范中心計算機學(xué)科組規(guī)劃教材算法設(shè)計與分析Python案例詳解微課視頻版算法(漸進)時間復(fù)雜度，一般表示為以下幾種數(shù)量級的形式(n為問題的規(guī)模，c為常量)：Ο(1)：常數(shù)級Ο(logn)：對數(shù)級Ο(n)：為線性級Ο(nc)：多項式級Ο(cn)：指數(shù)級Ο(n!)：階乘級定理1：對每個b>1和每個a>0，有l(wèi)ogbn=o(na)定理2：對每個r>1和每個d>0，有nd=o(rn)隨規(guī)模n的增長，時間復(fù)雜度級別可由低到高進行排列：

高效求解：O(1)、O(logn)；有效求解：O(nc)；難求解：O(2n)、O(n!)隨規(guī)模n的增長，時間復(fù)雜度級別可由低到高進行排列：

sec=seconds；s=10-6sec；ms=10-3sec；min=minutes；yr=years；hr=hours；d=days測試排序題。請按照時間復(fù)雜度從低到高的順序排序:()、()、()、()、()、()、() A：O(n2) B：O(1) C：O(logn) D：O(nlogn) E：O(2n) F：O(n!) G：O(n3)算法的選擇不能只依賴于時間復(fù)雜度，需要與實際工程相結(jié)合：算法1：F(n)=1000n2+100n算法2：G(n)=10n4一個具體算法的時間復(fù)雜度和空間復(fù)雜度往往不是獨立的，在算法設(shè)計中要在時間效率和空間效率之間折衷。

兩種策略：時間換空間、空間換時間。常用數(shù)學(xué)公式：

算術(shù)級數(shù)：

與末項平方同階，T(n)=1+2+3+...+n=O(n2)冪方級數(shù)：

比冪次高一階，T(n)=1+2d+3d...+nd=O(nd+1)等比數(shù)列：

與末項同階，T(n)=1+a+a2+...+an=O(an)收斂級數(shù)：

從1開始，一直遞減，每項都為正，T(n)=O(1)調(diào)和級數(shù)：

T(n)=1+1/2+1/3+1/4+...+1/n=

(logn)對數(shù)級數(shù)：

T(n)=log1+log2+log3+...+logn=log(n!)=

(nlogn)時間就是金錢，時間就是生命英格瑪（Enigma）密碼機密碼破譯機VS圖靈與破解Enigma密碼機的機器算法設(shè)計與分析算法分析-最優(yōu)性信息工程大學(xué)國家級實驗教學(xué)示范中心計算機學(xué)科組規(guī)劃教材算法設(shè)計與分析Python案例詳解微課視頻版什么是最優(yōu)性最優(yōu)性如何證明部分已知最優(yōu)算法一二三算法類－解決某一問題的各種算法中，用算法所執(zhí)行的基本操作對算法進行劃分，基本操作相同的算法為同類算法。最優(yōu)算法－若算法A在最壞情況（或平均情況）下是最優(yōu)的，是指：算法A所在的算法類中的其他算法，在最壞（或平均）情況下，執(zhí)行基本操作的次數(shù)不比A更少。最優(yōu)算法可能不只一個。注：以最壞情況說明：求基本操作次數(shù)：求解對尺寸為n的任何輸入，算法A至多做的基本操作次數(shù)W(n)。證明一個定理：算法類中的任何一個算法，在最壞情況下，至少做F(n)次基本操作。比較：若W(n)=F(n)，則A是該算法類中在最壞情況下的最優(yōu)算法，否則A不是最優(yōu)算法。問題：在n個不同項的表L中，尋找最大項?；静僮鳎罕碇袃身椀谋容^輸入：L，n；輸出：最大項Max

1．Max=L[1];i=2;2．whilei≤ndobegin3．

ifMax<L[i]thenMax=L[i];4．

i=i+1;5．end;6．printf(Max);對尺寸為n的任何輸入，該算法做n-1次“比較”，故W(n)=n–1。定理：在具有n個不同項的表中，以“比較操作”為基本操作的算法類中的任何一個算法，在最壞情況下，至少做n-1次比較操作。在n個不同項的表中，n-1個項不是最大項；對n-1個較小項中的任何一個，當(dāng)它至少比表中另外一項較小時，才能斷定它不是最大項；每一次比較只能確定一個較小項，當(dāng)且僅當(dāng)把n-1個較小項確定之后才能定出最大項，

故知：比較算法類中的任何算法，在最壞情況下，至少做n-1次比較，才能找到最大項。即F(n)=n-1。

證明：比較W(n)和F(n)知：算法在最壞情況下，是該算法類中的一個最優(yōu)算法。測試判斷題：所有算法之間都可以進行最優(yōu)性的比較分析A：正確B：錯誤以比較操作為基本操作，在最壞情況下：求無序序列中的最大（?。?shù)

最優(yōu)方法：窮舉法

時間復(fù)雜度：n-1求無序序列中的最大和最小數(shù)

最優(yōu)方法：分治法、淘汰賽法

時間復(fù)雜度：3n/2-2

求無序序列中的最大和次大數(shù)

最優(yōu)方法：分治法、淘汰賽法

時間復(fù)雜度：n+

logn

-2在一個有序序列中查找某個數(shù)

最優(yōu)方法：二分查找

時間復(fù)雜度：O(logn)在平均情況下：排序

最優(yōu)方法：快速排序、歸并排序

時間復(fù)雜度：O(nlogn)算法設(shè)計與分析算法分析-NP完全理論信息工程大學(xué)國家級實驗教學(xué)示范中心計算機學(xué)科組規(guī)劃教材算法設(shè)計與分析Python案例詳解微課視頻版時間復(fù)雜度：O(nc)時間復(fù)雜度：O(2n)多項式指數(shù)易解問題：能在多項式時間內(nèi)解決的問題難解問題：不存在多項式時間算法的問題問題分類：問題：都是判定問題判定問題是僅僅要求回答是或否的問題。計算問題：

給定一個整數(shù)集合，找到一個非空子集使得它的和為0（子集求和問題）。判定問題：

給定一個整數(shù)集合，是否存在一個非空子集使得它的和為0。計算問題：

找到一條從起點出發(fā)，經(jīng)過圖中每個頂點僅且一次又回到起點的回路，且該

回路上所花費的代價最?。═SP問題）。判定問題：是否存在一條回路，從起點出發(fā)，經(jīng)過圖中每個頂點僅且一次又回到起點，

且該回路上所花費的代價小于等于正整數(shù)k。P問題：

如果一個問題可以找到一個能在多項式的時間內(nèi)解決它的算法，那么這個問題就屬于P問題。

NP問題：NP問題不是非P類問題可以在多項式的時間里驗證一個解的問題

可以在多項式的時間里猜出一個解的問題問題1：子集求和問題

集合s={-1,3,2,-5,6}，子集{3,2,-5}問題2：問某圖中是否不存在Hamilton回路？問題1是NP問題問題2不是NP問題NP問題與P問題的關(guān)系：所有的P類問題都是NP問題：能多項式地解決一個問題，必然能多項式地驗證一個問題的解。

是否所有的NP問題都是P類問題？究竟是否有P=NP？P=NP不成立：存在不可能有多項式級復(fù)雜度的算法的NP問題。NPC問題：NP-完全問題多項式時間歸約：

考慮一個判定問題A，如果A的任意輸入都可以在多項式時間內(nèi)通過某個變換轉(zhuǎn)化成判定問題B的輸入，且問題B的計算結(jié)果與問題A的結(jié)果相同。一元一次方程一元二次方程Hamilton回路旅行售貨員問題（TSP）1.如果問題B存在多項式時間可解的算法，那么問題A也存在多項式時間可解的算法。2.如果不存在求解A的多項式時間的算法，那么也不存在求解問題B的多項式時間算法。NPC問題：首先，它得是一個NP問題；其次，所有的NP問題都可以歸約到它。證明：先證明它至少是一個NP問題；再證明其中一個已知的NPC問題能約化到它（由約化的傳遞性）。NP-Hard問題：它滿足NPC問題定義的第二條但不一定要滿足第一條。NPPNPCNP-Hard測試選擇題：以下說法正確的有（）A：p問題屬于NP問題B：問題A歸約為問題B后，問題B的求解難度更大C：NPC問題屬于NP問題D：ＮＰ－Ｈａｒｄ問題屬于ＮＰ問題算法設(shè)計與分析算法評價-總結(jié)信息工程大學(xué)國家級實驗教學(xué)示范中心計算機學(xué)科組規(guī)劃教材算法設(shè)計與分析Python案例詳解微課視頻版基本概念算法的定義和特征

算法設(shè)計與算法分析的關(guān)系

分析算法的五個準(zhǔn)則

最優(yōu)性的含義

最優(yōu)性的證明方法時間復(fù)雜度的分析方法非遞歸實現(xiàn)

確定基本操作

確定問題規(guī)模和輸入種類

按照公式求解平均時間復(fù)雜度和最壞時間復(fù)雜度

用漸近時間復(fù)雜度表示遞歸實現(xiàn)

迭代法

遞歸樹

主定理

性能測試方法理論和實踐相結(jié)合空間測試方法算法設(shè)計與分析程序測試信息工程大學(xué)國家級實驗教學(xué)示范中心計算機學(xué)科組規(guī)劃教材算法設(shè)計與分析Python案例詳解微課視頻版性能測試方法空間測試方法一二性能是衡量程序不可或缺的標(biāo)準(zhǔn)之一。性能測試結(jié)果直接反映算法在變?yōu)榫唧w程序后的運行時間。代碼2-1：性能測試代碼（時間：微妙）#導(dǎo)入庫importtime

#主函數(shù)if__name__=='__main__':start_time=time.time()

……

#yourcodesend_time=time.time()time_use

=(end_time-start_time)*1000000.0print('該程序運行時間：',time_use,"微秒")通過工具測試GprofVTune在Windows和Linux系統(tǒng)中，一般均可以通過操作系統(tǒng)的任務(wù)管理器或者進程監(jiān)聽命令查看程序所占用的內(nèi)存空間。算法設(shè)計與分析算法設(shè)計-遞歸信息工程大學(xué)國家級實驗教學(xué)示范中心計算機學(xué)科組規(guī)劃教材算法設(shè)計與分析Python案例詳解微課視頻版一二遞歸思想典型應(yīng)用階乘漢諾塔全排列整數(shù)劃分基本概率基本要素重點掌握：1.遞歸的思想2.遞歸的應(yīng)用算法設(shè)計與分析遞歸-基本思想信息工程大學(xué)國家級實驗教學(xué)示范中心計算機學(xué)科組規(guī)劃教材算法設(shè)計與分析Python案例詳解微課視頻版什么是遞歸典型問題舉例遞歸基本思想一二三遞歸算法：一個直接或間接調(diào)用自身的算法二叉樹定義：二叉樹是一棵空樹，或者是一棵由一個根節(jié)點和兩棵互不相交的，分別稱作根的左子樹和右子樹組成的非空樹構(gòu)成；左子樹和右子樹又同樣都是二叉樹。階乘問題n!=1n=0n(n-1)!n>0定義：n!=1·2·3·…·(n-1)·n算法描述：用intFact(intn)函數(shù)表示輸入：n輸出：n！1、ifn==0thenreturn1;2、returnn*Fact(n-1);階乘問題設(shè)n=5：intFact(intn)1、ifn==0thenreturn1;2、returnn*Fact(n-1);4*Fact(3)Fact(5)5*Fact(4)3*Fact(2)2*Fact(1)26241201遞推回歸1*Fact(0)1遞歸思想：把一個不好解決的大問題轉(zhuǎn)化為一個或幾個小問題再把這些小問題進一步分解成更小的小問題直至每個小問題都可以直接解決（5！的求解）（4！的求解）（3！的求解）（0！的求解）遞推方程+邊界條件遞歸基本要素：邊界條件：確定遞歸到何時終止，也稱為遞歸出口。遞歸模式：大問題如何分解為小問題，也稱為遞歸體。看似重復(fù)且無趣，實則有效且出彩遞歸中的重復(fù)計算日常中的重復(fù)工作日拱一卒，功不唐捐，偉大的成就，都是在重復(fù)中練成的。共和國勛章諾貝爾獎屠呦呦七一勛章張桂梅死磕自己，把重復(fù)做到極致，可能很慢，但最后總能到達測試選擇題：

遞歸的兩個基本要素是（）和（）。 A：邊界條件 B：遞推方程 C：實現(xiàn)方式算法設(shè)計與分析遞歸-典型應(yīng)用-漢諾塔信息工程大學(xué)國家級實驗教學(xué)示范中心計算機學(xué)科組規(guī)劃教材算法設(shè)計與分析Python案例詳解微課視頻版n階漢諾塔設(shè)A、B、C是三個塔座。開始時，在A上有一疊共n個自下而上，由大到小疊在一起的圓盤，這些圓盤從小到大編號為1,2,…,n?，F(xiàn)要求將A上的這一疊圓盤移到B上，并仍按同樣的順序疊放。ABC12…nn階漢諾塔移動規(guī)則：（1）每次只能移動一個圓盤；（2）任何時刻都不許將較大的圓盤壓在較小的圓盤之上；（3）在滿足移動規(guī)則(1)、(2)的前提下，可將圓盤移至A、B、C的任一塔座上。ABC12…nn階漢諾塔不完全歸納分析：（1）當(dāng)n=1時，將圓盤1從A直接移至B上。（2）當(dāng)n>1時，需要利用塔座C作為輔助塔座；將n-1個較小的圓盤依照規(guī)則從塔座A移動到塔座C；將剩下的最大圓盤從塔座A移至塔座B;將n-1個較小的圓盤依照規(guī)則從塔座C移至塔座B。n個圓盤移動問題分解為兩次n-1個圓盤移動問題。代碼3-1：漢諾塔問題的實現(xiàn)defMove(n,A,B):#輸出函數(shù)，第n個盤從A移動到Bprint(n,':',A,'-->',B)

defHanoi(n,A,B,C):#遞歸函數(shù)ifn>0:#遞歸出口Hanoi(n-1,A,C,B)Move(n,A,B)Hanoi(n-1,C,B,A)

if__name__=='__main__':A='A'B='B'C='C'n=int(input("請輸入圓盤個數(shù)："))Hanoi(n,A,B,C)n階漢諾塔測試選擇題：對于3階漢諾塔，一共需要移動圓盤7次，第5次移動操作是（） A：Move(2,A,C) B：Move(1,B,C) C：Move(3,A,B) D：Move(1,C,A)算法設(shè)計與分析遞歸-典型應(yīng)用-全排列信息工程大學(xué)國家級實驗教學(xué)示范中心計算機學(xué)科組規(guī)劃教材算法設(shè)計與分析Python案例詳解微課視頻版設(shè)R={r1,r2,…,rn}是要進行排列的n個元素，試設(shè)計一個算法，將這n個元素的全排列找出。以n=3為例，R={1，2，3}的全排列如下：1 2 33 21 33 11 23 2 1分析發(fā)現(xiàn)：1）每個元素分別作為排列的第一個元素；2）余下是（n-1）個元素的全排列；3）元素個數(shù)為1時，排列是它自身。R的全排列可歸納定義如下：n=1時，Perm(r)=(r),r是集合中唯一的元素。n>1時，Perm(R)由(r1)Perm(R1),(r2)Perm(R2),....,(rn)Perm(Rn)構(gòu)成。全排列問題中蘊涵的遞歸關(guān)系：設(shè)Ri=R-{ri}。集合Ri中元素的全排列記為Perm(Ri)。(ri)Perm(Ri)表示在全排列Perm(Ri)的每一個排列前加上前綴ri得到的排列。全排列輸出算法描述用一個形如Perm(inta[],intk,intm)的函數(shù)表示輸入：a數(shù)組，k,m輸出：a的第k到第m個元素的全排列1、ifk=mthen輸出a數(shù)組;else2、fori=ktomdobegin3、a[k]和a[i]互換；4、Perm(a,k+1,m);5、

a[k]和a[i]互換；end;6、return求a數(shù)組從1到n的全排列，執(zhí)行算法Perm(a,1,n)。a[3]={1,2,3}Perm(a,0,2)a[3]={1,2,3}Perm(a,1,2)a[3]={2,1,3}Perm(a,1,2)a[3]={3,2,1}Perm(a,1,2)a[3]={1,2,3}Perm(a,2,2)a[3]={1,3,2}Perm(a,2,2)a[3]={2,1,3}Perm(a,2,2)a[3]={2,3,1}Perm(a,2,2)a[3]={3,2,1}Perm(a,2,2)a[3]={3,1,2}Perm(a,