算法設(shè)計(jì)與分析 課件 第一章 緒論1.4.1 時(shí)間復(fù)雜度分析

計(jì)算機(jī)算法設(shè)計(jì)與分析第一章概述1.4.1算法的效率分析目的評(píng)估算法體現(xiàn)算法運(yùn)行時(shí)所需要消耗的計(jì)算機(jī)資源占用CPU的計(jì)算時(shí)間量稱為時(shí)間復(fù)雜度占用內(nèi)存的存儲(chǔ)空間量稱為空間復(fù)雜度算法復(fù)雜度分析一般采用事前分析方式而是不事后統(tǒng)計(jì)法算法的效率分析算法的時(shí)間復(fù)雜度T和空間復(fù)雜度S的函數(shù)：T=T(N,I)S=S(N,I)N表示問(wèn)題規(guī)模，I表示算法輸入在實(shí)際應(yīng)用中，關(guān)注時(shí)間效率多于空間效率。算法時(shí)間復(fù)雜度分析評(píng)估算法時(shí)間復(fù)雜度，應(yīng)盡量做到客觀反映算法的本質(zhì)特征和屬性。所以，算法時(shí)間復(fù)雜度分析應(yīng)該要有一個(gè)不依賴于計(jì)算機(jī)硬件配置、問(wèn)題規(guī)模和輸入實(shí)例的抽象表示。算法時(shí)間復(fù)雜度分析假設(shè)在一臺(tái)抽象的計(jì)算機(jī)上提供了k種元運(yùn)算O1，O2，…，Ok，每個(gè)元運(yùn)算執(zhí)行的時(shí)間分別為t1，t2，...，tk。元運(yùn)算通常指的是算法中最基本的操作步驟，一個(gè)元運(yùn)算可以是基本的算術(shù)運(yùn)算（如加法、減法、乘法、除法）、比較操作、賦值操作、數(shù)組訪問(wèn)或迭代循環(huán)等。算法時(shí)間復(fù)雜度分析T(N，I)表示算法在這臺(tái)抽象計(jì)算機(jī)上運(yùn)行所需要的的時(shí)間，設(shè)，在算法中

元運(yùn)算Oi被調(diào)用的次數(shù)為ei，ei=ei(N,I)，因此，T(N,I)一般化的表示：算法時(shí)間復(fù)雜度分析為消除公式中ti表示的元運(yùn)算執(zhí)行的具體時(shí)間，不妨假設(shè)所有的元運(yùn)算都在一個(gè)單位時(shí)間內(nèi)完成或者將ti抽象表示為一條執(zhí)行語(yǔ)句或表達(dá)式所用時(shí)間，則計(jì)算T(N,I)的工作就變?yōu)榻y(tǒng)計(jì)計(jì)算語(yǔ)句的頻度，從而簡(jiǎn)化復(fù)雜度的求解。例1.4插入排序問(wèn)題時(shí)間復(fù)雜度計(jì)算

算法：插入排序（升序排序）

輸入：數(shù)組元素array，元素個(gè)數(shù)n

輸出：升序的數(shù)組元素arrayInsertSort(array,n):begin1fori

1ton–1do2key

array[i]3j

i–14whilej>=0andarray[j]>keydo5array[j+1]

array[j]//往后移動(dòng)元素6 j

j–17 end8 array[j+1]

key9

endend當(dāng)輸入數(shù)據(jù)為1,2,3,4,5時(shí)，語(yǔ)句2、3、8被執(zhí)行4次，語(yǔ)句5、6被執(zhí)行0次。當(dāng)輸入數(shù)據(jù)為5,4,3,2,1時(shí)，語(yǔ)句2、3、8被執(zhí)行4次，語(yǔ)句5、6被執(zhí)行10次。算法時(shí)間復(fù)雜度分析對(duì)同一個(gè)算法，運(yùn)行不同的輸入實(shí)例時(shí)，算法語(yǔ)句執(zhí)行的次數(shù)差異明顯。實(shí)際上，在統(tǒng)計(jì)時(shí)間復(fù)雜度時(shí)，我們不可能對(duì)規(guī)模N的每一種合法輸入都去統(tǒng)計(jì)各個(gè)算法語(yǔ)句執(zhí)行的次數(shù)，這時(shí)就需要對(duì)輸入實(shí)例做一個(gè)合理簡(jiǎn)化，即將輸入實(shí)例進(jìn)行特化。算法時(shí)間復(fù)雜度分析（1）最壞情況下的時(shí)間復(fù)雜度：IN是規(guī)模為N的合法輸入集合，I*是IN中使T(N,I)達(dá)到Tmax(N)的合法輸入。最壞情況下的時(shí)間復(fù)雜度就是將所有的合法輸入實(shí)例中最壞的那個(gè)輸入實(shí)例I*找出來(lái)，統(tǒng)計(jì)在輸入實(shí)例I*時(shí)算法語(yǔ)句執(zhí)行的次數(shù)來(lái)評(píng)估算法時(shí)間復(fù)雜度。算法時(shí)間復(fù)雜度分析（2）最好情況下的時(shí)間復(fù)雜度：I'是IN中使T(N,I)達(dá)到Tmin(N)的合法輸入，將所有的合法輸入實(shí)例中最好的那個(gè)輸入實(shí)例I'找出來(lái)，統(tǒng)計(jì)在輸入實(shí)例I'時(shí)算法語(yǔ)句執(zhí)行的次數(shù)來(lái)評(píng)估算法時(shí)間復(fù)雜度。算法時(shí)間復(fù)雜度分析（3）平均情況下的時(shí)間復(fù)雜度：P(I)是算法應(yīng)用中出現(xiàn)輸入實(shí)例I的概率，全部合法輸入實(shí)例的概率總和為1。平均時(shí)間復(fù)雜度是用每一個(gè)輸入實(shí)例出現(xiàn)的概率，計(jì)算其數(shù)學(xué)期望。在分析算法時(shí)間復(fù)雜度的時(shí)候，往往關(guān)注的是最壞情況下算法的時(shí)間復(fù)雜度。例1.4插入排序問(wèn)題時(shí)間復(fù)雜度計(jì)算

算法：插入排序（升序排序）

輸入：數(shù)組元素array，元素個(gè)數(shù)n

輸出：升序的數(shù)組元素arrayInsertSort(array,n):begin1fori

1ton–1do2key

array[i]3j

i–14whilej>=0andarray[j]>keydo5array[j+1]

array[j]//往后移動(dòng)元素6 j

j–17 end8 array[j+1]

key9

endend語(yǔ)句2,3,8分別執(zhí)行N-1次語(yǔ)句5,6執(zhí)行的次數(shù)分為1,2,3，...，N-1次