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

下載本文檔

版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進(jìn)行舉報(bào)或認(rèn)領(lǐng)

文檔簡介

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

2、機(jī)器代碼質(zhì)量機(jī)器執(zhí)行指令的速度綜上所述,為便于比較算法本身的優(yōu)劣,應(yīng)排除其它 影響算法效率的因素。從算法中選取一種對于所研究的問題來說是基本操 作的原操作,以該基本操作重復(fù)執(zhí)行的次數(shù)作為算法 的時間量度。(原操作在所有該問題的算法中都相 同)T(n)= Qf( n)上示表示隨問題規(guī)模n的增大,算法執(zhí)行時間的增長 率和f(n)的增長率相同,稱作算法的 漸近時間復(fù)雜 度,簡稱時間復(fù)雜度。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í)行次數(shù)和包含它的語句的 頻度相同。語句的 頻度指的是該語句重復(fù)執(zhí)行的次數(shù)。語句頻度時間復(fù)雜度+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í)行次數(shù)不確定時的時間復(fù)雜度平均時間復(fù)雜度依基本操作執(zhí)行次數(shù)概率計(jì)算平均最壞情況下時間復(fù)雜度在最壞情況下基本操作執(zhí)行次數(shù)、算法的存儲空間需求 類似于算法的時間復(fù)雜度,空間復(fù)雜度可以作為算法所需存儲空間 的量度。記作:S(n)= Qf(n)若額外空間相對于輸入數(shù)據(jù)量來說是常數(shù),則稱此算法為原地工 作

溫馨提示

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

評論

0/150

提交評論