算法效率的度量和存儲空間需求_第1頁
算法效率的度量和存儲空間需求_第2頁
算法效率的度量和存儲空間需求_第3頁
算法效率的度量和存儲空間需求_第4頁
全文預覽已結束

下載本文檔

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

文檔簡介

1、第四課本課主題：算法效率的度量和存儲空間需求教學目的： 掌握算法的漸近時間復雜度和空間復雜度的意義與作用教學重點：漸近時間復雜度的意義與作用及計算方法教學難點：漸近時間復雜度的意義授課內容：一、算法效率的度量算法執(zhí)行的時間是算法優(yōu)劣和問題規(guī)模的函數。 評價一個算法的優(yōu) 劣，可以在相同的規(guī)模下，考察算法執(zhí)行時間的長短來進行判斷。而一個程序的執(zhí)行時間通常有兩種方法：1、事后統(tǒng)計的方法。缺點：不利于較大范圍內的算法比較。（異地，異時， 異境）2、事前分析估算的方法。程序在計算機上運行所需時間的影響因素算法本身選用的策略1問題的規(guī)模規(guī)模越大，消耗時間越多書寫程序的語言語言越高級，消耗時間越多編譯產生的

2、機器代碼質量機器執(zhí)行指令的速度綜上所述，為便于比較算法本身的優(yōu)劣，應排除其它 影響算法效率的因素。從算法中選取一種對于所研究的問題來說是基本操 作的原操作，以該基本操作重復執(zhí)行的次數作為算法 的時間量度。(原操作在所有該問題的算法中都相 同)T(n)= Qf( n)上示表示隨問題規(guī)模n的增大，算法執(zhí)行時間的增長 率和f(n)的增長率相同，稱作算法的 漸近時間復雜 度，簡稱時間復雜度。sum(int num44) int i,j,r=0;求4*4矩陣元for(i=0;i4;i+)素和，for(j=0;j4;j+)T=O(f(4)r+=numij; /*原操作f=n*n;*/return r;最好

3、情況：ispass(int num44)T( 4)=0( 0) int i,j;最壞情況：for(i=0;i4;i+)T (4) =O(n*n)for(j=0;j4;j+)if(n umij!=i*4+j+1)return 0;return 1;原操作執(zhí)行次數和包含它的語句的 頻度相同。語句的 頻度指的是該語句重復執(zhí)行的次數。語句頻度時間復雜度+x;s=0;1O(1)for(i=1;i=n;+i)+x;s+=x;nO(n)for(j=1;j=n;+j)for(k=1;k=n;+k)+x;s+=x;n*nO(n*n)O(log n)基本操作的執(zhí)行次數不確定時的時間復雜度平均時間復雜度依基本操作執(zhí)行次數概率計算平均最壞情況下時間復雜度在最壞情況下基本操作執(zhí)行次數、算法的存儲空間需求 類似于算法的時間復雜度，空間復雜度可以作為算法所需存儲空間 的量度。記作:S(n)= Qf(n)若額外空間相對于輸入數據量來說是常數，則稱此算法為原地工 作

溫馨提示

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

評論

0/150

提交評論