算法效率的度量和存儲空間需求

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ù)，則稱此算法為原地工 作