算法設(shè)計與分析1緒論

1、算法設(shè)計與分析2007.91基本情況性質(zhì)：必修學(xué)時：54考核方法：平時成績50考勤10專題或課堂報告40期末考試502教材和參考書教材（美）科曼（Cormen, T.H.）等著, 潘金貴 等譯. 算法導(dǎo)論（原書第2版）. 北京: 機(jī)械工業(yè)出版社, 2006.9參考資料Anany Levitin, (潘彥譯)算法設(shè)計與分析基礎(chǔ). 北京: 清華大學(xué)出版社, 2004.6Sara Baase等. 計算機(jī)算法-設(shè)計與分析導(dǎo)論(英文影印版). 北京: 高等教育出版社, 2001.7王曉東. 計算機(jī)算法設(shè)計與分析. 北京: 電子工業(yè)出版社, 2001.1 3主要內(nèi)容算法分析基本知識高級數(shù)據(jù)結(jié)構(gòu)堆/紅黑樹/

2、順序統(tǒng)計樹/區(qū)間樹/二項堆/斐波那契堆/分離集合 等算法設(shè)計及分析方法各種排序/動態(tài)規(guī)劃/貪心算法 等4第一章 緒論1.1 算法1.2 算法分析1.3 算法設(shè)計51.1 算法 什么是算法？算法的形式定義可以看作是任何一個良定義（有窮/確定/可行）的計算過程，以一個或一些值作為輸入，產(chǎn)生出一個或一組值作為輸出（問題陳述）。“computer” problemalgorithminputoutput61.1 算法 算法的重要性微積分造就了現(xiàn)代科學(xué)，算法造就了現(xiàn)代世界；算法是計算機(jī)科學(xué)的基石；算法：計算的靈魂程序算法數(shù)據(jù)結(jié)構(gòu)；學(xué)習(xí)算法可以開發(fā)人們的分析能力；71.1 算法 必要性知道計算機(jī)領(lǐng)域中解決

3、不同問題的一系列標(biāo)準(zhǔn)算法；具備設(shè)計新算法和分析其效率的能力81.1 算法 問題求解過程證明正確性分析算法設(shè)計程序理解問題精確解或近似解選擇數(shù)據(jù)結(jié)構(gòu)算法設(shè)計策略設(shè)計算法91.1 算法 兩種組織方法按照問題類型分類查找/排序/串處理/圖/組合問題/幾何問題/數(shù)值問題 等按照算法技術(shù)分類直接法/分治技術(shù)/貪婪技術(shù)/動態(tài)規(guī)劃/近似算法/分支定界法/回溯法/線性規(guī)劃/網(wǎng)絡(luò)流/概率算法/并行算法 等101.1 算法 算法舉例排序問題輸入：一列數(shù)輸出：輸入序列的一個變換，其中 a1 an算法選擇/冒泡/插入/快速/堆/算法的選取取決于多種因素111.1 算法 問題的實例及算法正確性問題實例由滿足問題陳述中所

4、給出限制，并能得到問題的一個結(jié)果的所有輸入構(gòu)成。對于排序問題，對輸入序列，排序算法的返回結(jié)果序列為，該輸入序列即為排序問題的一個實例。算法正確性對每一個輸入實例，一個算法都能停止并給出正確的答案，則該算法是正確的。我們說一個正確的算法解決了給定的計算問題。一個不正確的算法在其錯誤率可被控制的情況下可能是很有用的。121.1 算法 算法的描述-偽碼插入排序131.1 算法 算法的描述-偽碼插入排序141.1 算法 算法的描述-偽碼插入排序INSERTION-SORT(A) 1 for j 2 to lengthA2 do key Aj3 將Aj插入排好序的A1 . . j - 1中.4 i j

5、- 15 while i 0 and Ai key6 do Ai + 1 Ai7 i i - 18 Ai + 1 key151.1 算法 算法的描述-偽碼偽碼的使用約定縮進(jìn)用于表示程序體結(jié)構(gòu)；while, for, repeat, if等語句與Pascal中相同；符號表示后面部分是注釋；符號表示賦值操作；局部變量可不用聲明，全局變量必須聲明；數(shù)組中. . 表示數(shù)組下標(biāo)取值范圍，如A1.j；復(fù)合數(shù)據(jù)用對象來表示，對象的域的取值由域名后接方括號括住的對象名來表示；數(shù)組或?qū)ο笞兞勘豢醋魇侵赶驍?shù)組或?qū)ο蟮闹羔槪粎?shù)用按值傳遞方式傳給過程。161.2 算法分析 基本概念算法分析是指對算法所需的資源進(jìn)行預(yù)

6、測。算法”好”與”不好”?正確性時間效率空間效率是否存在更好的算法？下界最優(yōu)途徑理論/數(shù)學(xué)上的分析經(jīng)驗/計算機(jī)上的執(zhí)行情況171.2 算法分析 基本概念一個算法的運行時間是指在特定輸入時所執(zhí)行的基本操作數(shù)。一般地，算法的運行時間與輸入規(guī)模同步增長。即使規(guī)模相同的兩個不同輸入，其運行時間也可能差別很大。如插入排序算法中，輸入已排序的程度對算法的時間影響非常大。181.2 算法分析 插入排序算法假定每次執(zhí)行第i行所花的時間都是常量ci191.2 算法分析 插入排序算法總運行時間最佳運行時間（已排好序輸入）T(n) = c1n + c2 (n - 1) + c4 (n - 1) + c5 (n -

7、1) + c8 (n - 1) = (c1 + c2 + c4 + c8)n - (c2 + c4 + c5 + c8)=an+b線性函數(shù)201.2 算法分析 插入排序算法最壞情況運行時間（逆序輸入） =an2+bn+c二次函數(shù)21輸入情況選擇最壞情況分析（一般情況下）最壞情況運行時間是任何輸入下運行時間的上界；對某些算法，最壞情況是經(jīng)常發(fā)生的；“平均情況”的時間性常常與最壞情況下大致一樣。平均情況分析（特殊情況下）通常假定一個特定規(guī)模下的所有輸入的“平均性”都是一樣的；也可以采用隨機(jī)算法強制達(dá)到平均。1.2 算法分析 算法分析一般框架22時間的量度 增長量級忽略每條語句的真實代價（ci)忽略

8、低階項忽略最高次項的常數(shù)系數(shù)表示方法：(f(n)，如插入排序的最壞情況時間代價的階為(n2) 。如果一個算法的最壞情況運行時間的階比另一個算法低，一般認(rèn)為它更為有效：對足夠大規(guī)模的輸入，一個具有階(n2)的算法在最壞情況下比階為(n3)的算法運行的更快。1.2 算法分析 算法分析一般框架231.3 算法設(shè)計 設(shè)計方法直接法分治法減治法變治法貪婪技術(shù)動態(tài)規(guī)劃回溯/分支限界法241.3 算法設(shè)計 分治法最著名的通用算法設(shè)計技術(shù)策略：將原問題分成n個規(guī)模較小而結(jié)構(gòu)與原問題相似的子問題，遞歸地解這些子問題，然后合并其結(jié)果就得到原問題的解。步驟：分解（Divide）：將原問題分解成一系列子問題；解決（C

9、onquer）：遞歸地解各子問題。若子問題足夠小，則直接求解；合并（Combine）：將子問題的結(jié)果合并成原問題的解；關(guān)鍵在于合并處理251.3 算法設(shè)計 分治法-合并排序步驟：分解：將n個元素分成各含n/2個元素的子系列；解決：用合并排序法對兩個子序列遞歸地排序。如子序列長度為1時遞歸結(jié)束（已排好序）；合并：合并兩個已排序的子序列以得到排序結(jié)果；261.3 算法設(shè)計 分治法-合并排序MERGE-SORT(A,p,r)1 if p r2 then q (p + r)/23 MERGE-SORT(A,p,q)4 MERGE-SORT(A, q + 1, r)5 MERGE(A,p,q,r)271

10、.3 算法設(shè)計 分治法-合并排序281.3 算法設(shè)計 分治法-合并排序合并處理：如兩堆排好序的牌，合并成排好序的一堆。每次取出兩輸入堆中最上面的一張比較大小，將小的一張拿出到輸出堆中；重復(fù)上面的步驟直至某一輸入堆無牌；將另一輸入堆余下的牌依序放入輸出堆中。合并處理的時間代價為(n) （n=r-p+1，為待排序元素個數(shù)）291.3 算法設(shè)計 分治算法分析算法中含有對自身的遞歸調(diào)用時，其運行時間可用遞歸方程來表述。分治算法的遞歸式基于基本模式的三個基本步驟。設(shè)T(n)為在規(guī)模n下算法運行時間;設(shè)把原問題分解成a個子問題，每個的大小為原問題的1/b；設(shè)分解該問題和合并解的時間分別為D(n)和C(n)；如n足夠小時(n c)，則得到它的直接解的時間為常量，寫作(1) ，則：301.3 算法設(shè)計 分治法-合并排序分析簡化起見，假定原問題的規(guī)模是2的冪次；（后面可看到，該假定不影響遞歸式解的階）時間分析（給出遞歸形式的T(n)）：分解：D(n) = (1)；解決：遞歸解兩個規(guī)模為n/2的子問題，時間為2T(n/2)合并：C(n) = (n)。則：在第四章可知T(n)的階為(n lg n) （lgn代表log2n） 當(dāng)輸入規(guī)模足夠大時，優(yōu)于插入排