算法設計與分析 課件 1.3-算法分析準則 - 最優(yōu)性_第1頁
算法設計與分析 課件 1.3-算法分析準則 - 最優(yōu)性_第2頁
算法設計與分析 課件 1.3-算法分析準則 - 最優(yōu)性_第3頁
算法設計與分析 課件 1.3-算法分析準則 - 最優(yōu)性_第4頁
算法設計與分析 課件 1.3-算法分析準則 - 最優(yōu)性_第5頁
已閱讀5頁，還剩3頁未讀， 繼續(xù)免費閱讀

下載本文檔

版權說明：本文檔由用戶提供并上傳，收益歸屬內容提供方，若內容存在侵權，請進行舉報或認領

文檔簡介

算法設計與分析算法分析-最優(yōu)性信息工程大學國家級實驗教學示范中心計算機學科組規(guī)劃教材算法設計與分析Python案例詳解微課視頻版什么是最優(yōu)性最優(yōu)性如何證明部分已知最優(yōu)算法一二三算法類－解決某一問題的各種算法中，用算法所執(zhí)行的基本操作對算法進行劃分，基本操作相同的算法為同類算法。最優(yōu)算法－若算法A在最壞情況（或平均情況）下是最優(yōu)的，是指：算法A所在的算法類中的其他算法，在最壞（或平均）情況下，執(zhí)行基本操作的次數不比A更少。最優(yōu)算法可能不只一個。注：以最壞情況說明：求基本操作次數：求解對尺寸為n的任何輸入，算法A至多做的基本操作次數W(n)。證明一個定理：算法類中的任何一個算法，在最壞情況下，至少做F(n)次基本操作。比較：若W(n)=F(n)，則A是該算法類中在最壞情況下的最優(yōu)算法，否則A不是最優(yōu)算法。問題：在n個不同項的表L中，尋找最大項?；静僮鳎罕碇袃身椀谋容^輸入：L，n；輸出：最大項Max

1．Max=L[1];i=2;2．whilei≤ndobegin3．

ifMax<L[i]thenMax=L[i];4．

i=i+1;5．end;6．printf(Max);對尺寸為n的任何輸入，該算法做n-1次“比較”，故W(n)=n–1。定理：在具有n個不同項的表中，以“比較操作”為基本操作的算法類中的任何一個算法，在最壞情況下，至少做n-1次比較操作。在n個不同項的表中，n-1個項不是最大項；對n-1個較小項中的任何一個，當它至少比表中另外一項較小時，才能斷定它不是最大項；每一次比較只能確定一個較小項，當且僅當把n-1個較小項確定之后才能定出最大項，

故知：比較算法類中的任何算法，在最壞情況下，至少做n-1次比較，才能找到最大項。即F(n)=n-1。

證明：比較W(n)和F(n)知：算法在最壞情況下，是該算法類中的一個最優(yōu)算法。測試判斷題：所有算法之間都可以進行最優(yōu)性的比較分析A：正確B：錯誤以比較操作為基本操作，在最壞情況下：求無序序列中的最大（小）數

最優(yōu)方法：窮舉法

時間復雜度：n-1求無序序列中的最大和最小數

最優(yōu)方法：分治法、淘汰賽法

時間復雜度：3n/2-2

求無序序列中的最大和次大數

最優(yōu)方法：分治法、淘汰賽法

時間復雜度：n+

logn

-2在一個有序序列中查找某個數

最優(yōu)方法：二分查找

時間復雜度：O(lo

溫馨提示

  • 1. 本站所有資源如無特殊說明，都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等，如果需要附件，請聯(lián)系上傳者。文件的所有權益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙，網頁內容里面會有圖紙預覽，若沒有圖紙預覽就沒有圖紙。
  • 4. 未經權益所有人同意不得將文件中的內容挪作商業(yè)或盈利用途。
  • 5. 人人文庫網僅提供信息存儲空間，僅對用戶上傳內容的表現(xiàn)方式做保護處理，對用戶上傳分享的文檔內容本身不做任何修改或編輯，并不能對任何下載內容負責。
  • 6. 下載文件中如有侵權或不適當內容，請與我們聯(lián)系，我們立即糾正。
  • 7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

評論

0/150

提交評論