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

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

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