算法復(fù)雜性和常見問題

算法復(fù)雜性和常見問題第一頁，共二十二頁，2022年，8月28日第1章算法復(fù)雜性和常用數(shù)學(xué)工具1.運(yùn)行時(shí)間的上界、下界和準(zhǔn)確界2.最優(yōu)算法3.常見問題第二頁，共二十二頁，2022年，8月28日1.運(yùn)行時(shí)間的上界、下界和準(zhǔn)確界1.1運(yùn)行時(shí)間的上界1.2運(yùn)行時(shí)間的下界1.3運(yùn)行時(shí)間的準(zhǔn)確界1.4更小階和常見復(fù)雜度類型第三頁，共二十二頁，2022年，8月28日1.1運(yùn)行時(shí)間的上界函數(shù)f(n)和g(n)都是整數(shù)到正實(shí)數(shù)集合的映射，如果存在正整數(shù)n0和正常數(shù)c，使得對所有n≥n0，都有f(n)≤cg(n)，就稱f(n)的階至多是O(g(n))。這個(gè)定義的意義是：f(n)的增長至多像g(n)那樣快。例如，f(n)=2n2+3,g(n)=n2。則可以取n0=3，c=3。第四頁，共二十二頁，2022年，8月28日1.2運(yùn)行時(shí)間的下界函數(shù)f(n)和g(n)都是整數(shù)到正實(shí)數(shù)集合的映射，如果存在正整數(shù)n0和正常數(shù)c，使得對所有n≥n0，都有f(n)≥cg(n)，就稱f(n)的階至少是?(g(n))。這個(gè)定義的意義是：f(n)的增長至少像g(n)那樣快。例如，f(n)=2n2+3,g(n)=n2。則可以取n0=1，c=2。第五頁，共二十二頁，2022年，8月28日1.3運(yùn)行時(shí)間的準(zhǔn)確界函數(shù)f(n)和g(n)都是整數(shù)到正實(shí)數(shù)集合的映射，如果存在正整數(shù)n0和正常數(shù)c1和c2（c1≤c2）

，使得對所有n≥n0，都有c1g(n)≤f(n)≤c2g(n)，就稱f(n)的階是Θ(g(n))。這個(gè)定義的意義是：f(n)的增長像g(n)一樣快。關(guān)系“具有相同準(zhǔn)確界”構(gòu)成一個(gè)等價(jià)類—滿足自反性、對稱性和傳遞性（試證傳遞性）例如，f(n)=2n2+3,g(n)=n2。則可以取n0=3，c1=1，c2=3。第六頁，共二十二頁，2022年，8月28日1.4更小階和常見復(fù)雜度類型函數(shù)f(n)和g(n)都是整數(shù)到正實(shí)數(shù)集合的映射，如果對于任意正常數(shù)c，都存在正整數(shù)nc，使得對所有n≥n0，都有f(n)<cg(n)，就稱f(n)是g(n)的更小階，記做f(n)=o(g(n))。這個(gè)定義的意義是：f(n)的增長比g(n)的增長慢。例如，f(n)=2n2+3,g(n)=n3。1?loglogn?logn?n1/2?n3/4?n?nlogn?n2?2n?n!?2n^2第七頁，共二十二頁，2022年，8月28日練習(xí)f(n)=∑nj=1logj的復(fù)雜度與nlogn等價(jià)。推論：log(n!)=Θ(nlogn)第八頁，共二十二頁，2022年，8月28日2.最優(yōu)算法如果能夠證明求解問題∏的任何算法的運(yùn)行時(shí)間是?(f(n))，那么，以O(shè)(f(n))時(shí)間求解問題的任何算法，都認(rèn)為是最優(yōu)的。例如，如果數(shù)組中有n個(gè)元素，任何基于比較的排序，其復(fù)雜度下界為?(nlogn)。因?yàn)榫哂衝!個(gè)葉子節(jié)點(diǎn)的二叉樹的高度為log(n!)基于原理：log(n!)=Θ(nlogn)第九頁，共二十二頁，2022年，8月28日3.常見問題3.1最大子段和問題3.2找錢問題3.3背包問題3.4TSP問題3.5n皇后問題3.6假幣問題3.7凸包問題3.8平面上的最近點(diǎn)問題3.9排序問題3.10多段最短路徑問題3.11任務(wù)分配問題其它……第十頁，共二十二頁，2022年，8月28日3.1最大子段和問題給定n個(gè)整數(shù)（可以是0、可正、可負(fù)）組成的序列a1,a2,…,an,求該序列形如的子段和的最大值。例如，當(dāng)序列為{-2,11,-4,13,-5,-2}時(shí)，最大子段和為第十一頁，共二十二頁，2022年，8月28日3.2找錢問題一套錢幣有幾種不同的面值構(gòu)成。如果機(jī)器自動給顧客找錢，請給出一種策略，使得錢幣的數(shù)量最少。例如，假設(shè)一套錢幣共有10分、5分、1分的面值構(gòu)成，要找給顧客1角5分錢，一種顯然的方案是：10*1+5*1=15，共需要錢幣2個(gè)。這是一個(gè)最優(yōu)方案。如果這套錢幣的構(gòu)成是11分、5分和1分，同樣要找給顧客1角5分錢，則最優(yōu)方案是什么？第十二頁，共二十二頁，2022年，8月28日3.3背包問題背包問題：給定n種物品和一個(gè)背包，物品i的重量是wi,其價(jià)值為vi,背包的容量為C。如何選擇裝入背包的物品，使得背包中物品總價(jià)值最大？0-1背包問題：如果背包問題的每一種物品都不能分割：要么裝入，要么不裝入，不能裝入一部分，又該如何選擇物品，使得裝入背包后總價(jià)值最大？0-1背包問題的特例：物品價(jià)值和重量成正比。例如，設(shè)有n=8個(gè)體積分別為54，45，43，29，23，21，14，1的物體和一個(gè)容積為C=110的背包，問選擇哪幾個(gè)物體裝入背包可以使其裝得最滿。（最優(yōu)解：43+23+29+14+1=110）第十三頁，共二十二頁，2022年，8月28日3.4TSP問題旅行家要旅行n個(gè)城市然后回到出發(fā)的城市，要求各個(gè)城市經(jīng)歷且僅經(jīng)歷一次，并要求所走的路程最短。這個(gè)問題又稱為貨郎擔(dān)問題、郵遞員問題、售貨員問題。abcd237815一條最優(yōu)路徑是：a->b->d->c->a第十四頁，共二十二頁，2022年，8月28日3.5n皇后問題(待續(xù))8皇后問題是高斯1850年提出的一個(gè)著名問題：國際象棋中的“皇后”在橫向、直向、和斜向都能走步和吃子，問在8×8=64格的棋盤上如何能擺上八個(gè)皇后而使她們都不能互相吃?，F(xiàn)已知此問題共有92種解，但只有12種是獨(dú)立的，其余的都可以由這12種利用對稱性或旋轉(zhuǎn)而得到。n皇后問題：如果棋盤是n×n的格的，又如何擺放這些皇后？下面是4皇后問題的答案：第十五頁，共二十二頁，2022年，8月28日3.5n皇后問題(續(xù))1#主對角線3#主對角線5#主對角線0#次對角線2#次對角線4#次對角線6#次對角線1#次對角線3#次對角線5#次對角線0#主對角線2#主對角線4#主對角線6#主對角線01230123第十六頁，共二十二頁，2022年，8月28日3.6假幣問題一堆錢幣共有n個(gè)，其中一個(gè)是假幣，比其他錢幣輕，給你一架沒有砝碼的天平，如何用最少的次數(shù)把假幣找出來？如果事先只知道假幣和真幣不一樣中，而不知道它是輕還是重呢？如果是這種情況，給你12個(gè)錢幣，其中一個(gè)是假幣，你能使用天平3次把假幣找出嗎？第十七頁，共二十二頁，2022年，8月28日3.7凸包問題給定n個(gè)點(diǎn)構(gòu)成的平面上的點(diǎn)集，求出其凸包凸包是包含點(diǎn)集的最小凸集最小的意義是：其它凸集若能覆蓋點(diǎn)集，則能覆蓋凸包平面上的凸集是這樣的集合：凸集上任意兩點(diǎn)間線段上的任意一點(diǎn)都屬于該集合凸包有一個(gè)重要的性質(zhì)：凸包是由某些點(diǎn)構(gòu)成的多邊形注意不用人的直覺，而是用計(jì)算機(jī)怎樣解決這個(gè)問題！第十八頁，共二十二頁，2022年，8月28日3.8平面上的最近點(diǎn)問題一個(gè)二維平面上給出n個(gè)點(diǎn)，如何找到這n的點(diǎn)之間的存在的最小距離？有沒有小于O(n2)的方案？第十九頁，共二十二頁，2022年，8月28日3.9排序問題怎樣給一個(gè)一維數(shù)組快速排序？你目前能想到幾種辦法？復(fù)雜度分別是多少？堆排序是怎樣操作的？第二十頁，共二十二頁，2022年，8月28日3.10多段最短路徑問題多段圖是一個(gè)帶權(quán)的有向連通圖，頂點(diǎn)能夠劃分為k部分，第一部分和第k部分各是一個(gè)頂點(diǎn)，分別是始點(diǎn)和終點(diǎn)，第j部分結(jié)點(diǎn)發(fā)出的所有有向弧都指向了第j+1部分的結(jié)點(diǎn)。要求在多段圖中尋找一條從始點(diǎn)到終點(diǎn)的路徑，使得路徑的權(quán)值之和最小。下例的最優(yōu)值是160123456789423988874756866573第二十