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

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

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