1、算法設(shè)計與分析,譚守標(biāo) 安徽大學(xué) 電子學(xué)院 2007.9,基本情況,性質(zhì)：必修 學(xué)時：54 考核方法： 平時成績50 考勤10 專題或課堂報告40 期末考試50,教材和參考書,教材 （美）科曼（Cormen, T.H.）等著, 潘金貴 等譯. 算法導(dǎo)論（原書第2版）. 北京: 機(jī)械工業(yè)出版社, 2006.9 參考資料 Anany Levitin, (潘彥譯)算法設(shè)計與分析基礎(chǔ). 北京: 清華大學(xué)出版社, 2004.6 Sara Baase等. 計算機(jī)算法-設(shè)計與分析導(dǎo)論(英文影印版). 北京: 高等教育出版社, 2001.7 王曉東. 計算機(jī)算法設(shè)計與分析. 北京: 電子工業(yè)出版社, 2001

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

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

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

5、. . j - 1中. 4 i j - 1 5 while i 0 and Ai key 6 do Ai + 1 Ai 7 i i - 1 8 Ai + 1 key,1.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ù)用按值傳遞方式傳給過程。,

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

7、n) = c1n + c2 (n - 1) + c4 (n - 1) + c5 (n - 1) + c8 (n - 1) = (c1 + c2 + c4 + c8)n - (c2 + c4 + c5 + c8) =an+b,線性函數(shù),1.2 算法分析 插入排序算法,最壞情況運(yùn)行時間（逆序輸入） =an2+bn+c,二次函數(shù),輸入情況選擇 最壞情況分析（一般情況下） 最壞情況運(yùn)行時間是任何輸入下運(yùn)行時間的上界； 對某些算法，最壞情況是經(jīng)常發(fā)生的； “平均情況”的時間性常常與最壞情況下大致一樣。 平均情況分析（特殊情況下） 通常假定一個特定規(guī)模下的所有輸入的“平均性”都是一樣的； 也可以采用隨機(jī)算

8、法強(qiáng)制達(dá)到平均。,1.2 算法分析 算法分析一般框架,時間的量度 增長量級 忽略每條語句的真實代價（ci) 忽略低階項 忽略最高次項的常數(shù)系數(shù) 表示方法：(f(n)，如插入排序的最壞情況時間代價的階為(n2) 。 如果一個算法的最壞情況運(yùn)行時間的階比另一個算法低，一般認(rèn)為它更為有效：對足夠大規(guī)模的輸入，一個具有階(n2)的算法在最壞情況下比階為(n3)的算法運(yùn)行的更快。,1.2 算法分析 算法分析一般框架,1.3 算法設(shè)計 設(shè)計方法,直接法 分治法 減治法 變治法 貪婪技術(shù) 動態(tài)規(guī)劃 回溯/分支限界法 ,1.3 算法設(shè)計 分治法,最著名的通用算法設(shè)計技術(shù) 策略：將原問題分成n個規(guī)模較小而結(jié)構(gòu)與

9、原問題相似的子問題，遞歸地解這些子問題，然后合并其結(jié)果就得到原問題的解。 步驟： 分解（Divide）：將原問題分解成一系列子問題； 解決（Conquer）：遞歸地解各子問題。若子問題足夠小，則直接求解； 合并（Combine）：將子問題的結(jié)果合并成原問題的解；,關(guān)鍵在于合并處理,1.3 算法設(shè)計 分治法-合并排序,步驟： 分解：將n個元素分成各含n/2個元素的子系列； 解決：用合并排序法對兩個子序列遞歸地排序。如子序列長度為1時遞歸結(jié)束（已排好序）； 合并：合并兩個已排序的子序列以得到排序結(jié)果；,1.3 算法設(shè)計 分治法-合并排序,MERGE-SORT(A,p,r) 1 if p r 2 t

10、hen q (p + r)/2 3 MERGE-SORT(A,p,q) 4 MERGE-SORT(A, q + 1, r) 5 MERGE(A,p,q,r),1.3 算法設(shè)計 分治法-合并排序,1.3 算法設(shè)計 分治法-合并排序,合并處理： 如兩堆排好序的牌，合并成排好序的一堆。 每次取出兩輸入堆中最上面的一張比較大小，將小的一張拿出到輸出堆中； 重復(fù)上面的步驟直至某一輸入堆無牌； 將另一輸入堆余下的牌依序放入輸出堆中。 合并處理的時間代價為(n) （n=r-p+1，為待排序元素個數(shù)）,1.3 算法設(shè)計 分治算法分析,算法中含有對自身的遞歸調(diào)用時，其運(yùn)行時間可用遞歸方程來表述。 分治算法的遞歸

11、式基于基本模式的三個基本步驟。 設(shè)T(n)為在規(guī)模n下算法運(yùn)行時間; 設(shè)把原問題分解成a個子問題，每個的大小為原問題的1/b； 設(shè)分解該問題和合并解的時間分別為D(n)和C(n)； 如n足夠小時(n c)，則得到它的直接解的時間為常量，寫作(1) ，則：,1.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)于