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

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

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

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

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

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

1ton–1do2key

array[i]3j

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

array[j]//往后移動元素6 j

j–17 end8 array[j+1]

key9

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

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

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

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

1ton–1do2key

array[i]3j

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

array[j]//往后移動元素6 j

j–17 end8 array[j+1]

key9

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