算法分析的基本概念和方法(編輯修改稿)
2025-06-17 22:06 本頁(yè)面
【文章內(nèi)容簡(jiǎn)介】 但是， f(n)??(g(n)) 因此， f(n)? ?(g(n)) 此時(shí)，記作 O(f(n)) O(g(n))。 四、舉例 . 分析復(fù)雜度的基本步驟 各種復(fù)雜度比較示意圖如下。 五、復(fù)雜度比較示意圖 . 分析復(fù)雜度的基本步驟 各種復(fù)雜度比較示意圖如下。 五、復(fù)雜度比較示意圖 . 復(fù)雜度的有關(guān)概念 一、算法時(shí)間復(fù)雜度 ? 對(duì)于算法的時(shí)間復(fù)雜度，通常從分平均、最壞、最好幾種情形來(lái)衡量，尤其是前兩種。 ? 算法的平均復(fù)雜性 設(shè) Dn是對(duì)于所考慮問(wèn)題來(lái)說(shuō)大小為 n的輸入的集合，并設(shè) i是 Dn的一個(gè)元素， p(i)是 i出現(xiàn)的概率， t(i)是算法在輸入 i時(shí)所執(zhí)行的基本運(yùn)算次數(shù)。那么，算法的平均復(fù)雜性定義為： A(n)= ? i∈ Dn p(i)t(i) ? 算法的最壞復(fù)雜性 W(n)= MAX i∈ Dnt(i) ? 算法的最好復(fù)雜性 B(n)= MIN i∈ Dnt(i) . 復(fù)雜度的有關(guān)概念 [例 1] 檢索問(wèn)題的順序查找算法 。 以元素的比較作為基本操作。考慮成功檢索的情況。 最好情況下的時(shí)間復(fù)雜度： ?(1) 最壞情況下的時(shí)間復(fù)雜度： ?(n) 在等概率前提下，平均情況下的時(shí)間復(fù)雜度： ?(n) 二、舉例 算法分析方法 ? 例：順序搜索算法 templateclass Type int seqSearch(Type *a, int n, Type k) { for(int i=0。in。i++) if (a[i]==k) return i。 return 1。 } （ 1） Tmax(n) = max{ T(i) | size(i)=n }=O(n) （ 2） Tmin(n) = min{ T(i) | size(i)=n }=O(1) （ 3）在平均情況下，假設(shè)： (a) 搜索成功的概率為 p ( 0 ? p ? 1 )； (b) 在數(shù)組的每個(gè)位置 i ( 0 ? i n )搜索成功的概率相同，均為 p/n。 ???nIs i z eav g ITIpnT)()()()(? ?pnnpnnpnpnp ????????? ????????? 1321 ?? ? )1(2 )1(11pnnppninpni??????? ??. 復(fù)雜度的有關(guān)概念 [例 2] 直接插入排序算法 。 以元素的比較作為基本操作。 最好情況下的時(shí)間復(fù)雜度： ?(n) 最壞情況下的時(shí)間復(fù)雜度： 在等概率前提下，平均情況下的時(shí)間復(fù)雜度： 二、舉例 )( 2n?)( 2n?算法分析的基本法則 ? 非遞歸算法： （ 1） for / while 循環(huán) 循環(huán)體內(nèi)計(jì)算時(shí)間 *循環(huán)次數(shù)； （ 2）嵌套循環(huán) 循環(huán)體內(nèi)計(jì)算時(shí)間 *所有循環(huán)次數(shù)； （ 3）順序語(yǔ)句 各語(yǔ)句計(jì)算時(shí)間相加； （ 4） ifelse語(yǔ)句 if語(yǔ)句計(jì)算時(shí)間和 else語(yǔ)句計(jì)算時(shí)間的較大者。 templateclass Type void insertion_sort(Type *a, int n) { Type key。 // cost times for (int i = 1。 i n。 i++){ // c1 n key=a[i]。
環(huán)評(píng)公示相關(guān)推薦
鄂ICP備17016276號(hào)-1