算法導論復習資料-展示頁
2024-08-20 10:50本頁面
【正文】 會得到一個或多個有待解決的子問題；2）假設(shè)對一個給定的問題，已知的是一個可以導致最優(yōu)解的選擇，不必關(guān)心如何確定這個選擇，盡管假定它是已知的；3）在已知這個選擇后，要確定哪些子問題會隨之發(fā)生，以及如何最好地描述所得到的子問題的空間；4）利用一種“剪切粘貼法”，來證明在問題的一個最優(yōu)解中，使用的子問題的解本身也必須是最優(yōu)的?？键c：最優(yōu)子結(jié)構(gòu)性質(zhì)，自底向上填表計算最優(yōu)解值，導出最優(yōu)解。復雜度分析：分分治算法中的遞歸式是基于基本模式中的三個步驟的，T(n)為一個規(guī)模為n的運行時間，得到遞歸式T(n)=Q(1) n=cT(n)=aT(n/b)+D(n)+C(n) nc附加習題：請給出一個運行時間為Q(nlgn)的算法，使之能在給定的一個由n個整數(shù)構(gòu)成的集合S和另一個整數(shù)x時，判斷出S中是否存在有兩個其和等于x的元素。解：基本步驟：一、分解：將原問題分解成一系列的子問題；二、解決：遞歸地解各子問題?！S多問題都可以遞歸求解考點：快速排序，歸并排序，漸進排序，例如：12球里面有一個壞球，怎樣用最少的次數(shù)找出來。歸并排序的正確性分析：課本20頁。插入排序算法：INSERTIONSORT(A)1 for j ← 2 to length[A]2 do key ← A[j]3 ? Insert A[j] into the sorted sequence A[1，j 1].4 i ← j 15 while i 0 and A[i] key6 do A[i + 1] ← A[i]7 i ← i 18 A[i + 1] ← key插入排序的正確性證明：課本11頁。替換法證明，先猜想，然后給出遞歸方程）。正確性證明。算法導論復習資料——軟件0902 高超算法導論復習資料一、選擇題：第一章的概念、術(shù)語。二、考點分析：復雜度的漸進表示，復雜度分析?？键c：1）正確性分析（冒泡，歸并，選擇）；2）復雜度分析（漸進表示O，Ｑ，169。循環(huán)不變性的三個性質(zhì)：1）初始化：它在循環(huán)的第一輪迭代開始之前，應(yīng)該是正確的；2）保持：如果在循環(huán)的某一次迭代開始之前它是正確的，那么，在下一次迭代開始之前，它也應(yīng)該保持正確；3）當循環(huán)結(jié)束時，不變式給了我們一個有用的性質(zhì)，它有助于表明算法是正確的。歸并排序算法：課本17頁及19頁。分治法（基本步驟，復雜度分析）。（解：共有24種狀態(tài)，至少稱重3次可以找出不同的球）不是考點：線性時間選擇，最接近點對，斯特拉算法求解。若子問題足夠小，則直接求解；三、合并：將子問題的結(jié)果合并成原問題的解。動態(tài)規(guī)劃（最優(yōu)子結(jié)構(gòu)性質(zhì)，自底向上填表計算最優(yōu)解值（即最長公共子序列），導出最優(yōu)解）。a）動態(tài)規(guī)劃算法設(shè)計的4個步驟：1）描述最優(yōu)解的結(jié)構(gòu)；2）遞歸定義最優(yōu)解的值；3）按自底向上的方式計算最優(yōu)解的值；4）由計算出的結(jié)果構(gòu)造一個最優(yōu)解。備注：A problem exhibits optimal substructure if an optimal solution to the problem contains within it optimal solutions to subproblems. Whenever a problem exhibits optimal substucture it is a good clue that dynamic programming might apply. c）最長公共子序列的算法：這里以兩個序列X={x1,x2,…,xm}和Y={y1,y2,…,yn}為輸入，注意課本211頁的自底向上填表方法。MATRIXCHAINORDER(p) 每個表項的復雜度是O（n），共有O（n^2）表項，則為O（n^3）1 n ← length[p] 1 2 for i ← 1 to n 3 do m[i, i] ← 0 4 for l ← 2 to n ?l is the chain length. 5 do for i ← 1 to n l + 1 6 do j ← i + l 1 7 m[i, j] ← ∞ 8 for k ← i to j 1 9 do q ← m[i, k] + m[k + 1, j] + pi1 pkpj 10 if q m[i, j] 11 then m[i, j] ← q 12 s[i, j] ← k 13 return m and s PRINTOPTIMALPAREN
電大資料相關(guān)推薦
鄂ICP備17016276號-1