計算機算法設(shè)計與分析--第1章算法概述(編輯修改稿)
2024-11-15 10:17 本頁面
【文章內(nèi)容簡介】 | size(I)=n } ? 平均情況 下的時間復(fù)雜性 Tavg(n) = ? 其中 I是問題的規(guī)模為 n的實例， p(I)是實例 I出現(xiàn)的概率 。 ?? nIs iz eITIp)()()(34 時間復(fù)雜性計算 ?為了能夠較客觀的反映出一個算法的效率，在度量一個算法的工作量時，不僅應(yīng)該與所使用的計算機、程序設(shè)計語言以及程序編制者無關(guān)，而且還應(yīng)該與算法實現(xiàn)過程中的許多細節(jié)無關(guān)。為此，可以用算法在執(zhí)行過程中所需基本運算的執(zhí)行次數(shù)來度量算法的工作量?；具\算反映了算法運算的主要特征，因此，用基本運算的次數(shù)來度量算法工作量是客觀的也是實際可行的，有利于比較同一問題的幾種算法的優(yōu)劣。 ?例如，在考慮兩個矩陣相乘時，可以將兩個實數(shù)之間的乘法運算作為基本運算 . 35 時間復(fù)雜性計算 ? 在一般的計算機系統(tǒng)中，基本的運算和操作有以下四類： ①算術(shù)運算：主要包括加、減、乘、除等運算。 ②邏輯運算：主要包括“與”、“或”、“非”等運算。 ③關(guān)系運算：主要包括“大于”、“小于”、“等于”、“不等于”等運算。 ④數(shù)據(jù)傳輸：主要包括賦值、輸入、輸出等操作。 ?規(guī)定其中每條指令所需的時間都為常量。 算法的執(zhí)行時間 = 原子操作的執(zhí)行次數(shù) 原子操作的執(zhí)行時間 ?36 templateclass Type void InsertionSort(Type *a, int n) { Type key。 // cost times for (int i = 1。 i n。 i++){ // c1 n key=a[i]。 // c2 n1 int j=i1。 // c3 n1 while( j=0 amp。amp。 a[j]key ){ // c4 sum of ti a[j+1]=a[j]。 // c5 sum of (ti1) j。 // c6 sum of (ti1) } a[j+1]=key。 // c7 n1 } } 時間復(fù)雜性計算 37 ? 在最好情況下， ti=1, for 1 ? i n。 ? 在最壞情況下， ti ＝ i+1, for 1 ? i n。 )1()1()1()1()1()( 7116115114321 ???????????? ?????????nctctctT niiniinii)1()1()1()1()( 74321m i n ????????? nTbancccccccc??????????? )()( 743274321??? ????11 12 )1()1(ni nni?????11 2)1(ninnicbnanccccccccccccncnncnncnncnT??????????????????????????????? ???????? ????????????????27432765432126547654321m a x)(22)1(2)1(2)1(12)1()1()1()( 時間復(fù)雜性計算 38 算法的時間復(fù)雜度 ?如果目標是把 n個元素的序列升序排列，那么采用插入排序存在最好情況和最壞情況。 ?最好情況就是，序列已經(jīng)是升序排列了，在這種情況下，需要進行的比較操作需 (n1)次即可。 ?最壞情況就是，序列是降序排列，那么此時需要進行的比較共有 n(n1)/2次。插入排序的賦值操作是比較操作的次數(shù)加上 (n1)次。平均來說插入排序算法的時間復(fù)雜度為 O(n2)。 ?因而，插入排序不適合對于數(shù)據(jù)量比較大的排序應(yīng)用。但是，如果需要排序的數(shù)據(jù)量很小，例如，量級小于千，那么插入排序還是一個不錯的選擇。 39 復(fù)雜性分析的簡化 ?令 T(N)為表示算法 A的復(fù)雜性函數(shù)，若存在 ? (N)，使得 Lim N?? (T(N) – ?(N)) / T(N) = 0 那么，就可以用 ?(N)來代替 T(N) ，從而簡化復(fù)雜性的分析。 ? 例如： T(N) = 3N2+4NlogN+7， ?(N) = 3N2，則 Lim N?? (T(N) – ?(N)) / T(N) = Lim N?? 4NlogN+7 / 3N2+4NlogN+7 = 0 40 用階來表示復(fù)雜性 ?在漸進復(fù)雜性分析中，只要關(guān)心 ?(N)的階就夠了，不必關(guān)心 ?(N)中的常數(shù)因子，這樣我們就只需要用 ?(N)的階來表示該算法的復(fù)雜性。 ?例如，計算一個 N維矩陣 A的平方的時間復(fù)雜性可估算為 2N*N2 = 2N3，即此計算的時間復(fù)雜性為 3階。 41 時間復(fù)雜性的漸近性態(tài) ? 時間復(fù)雜性的漸近性態(tài)： (T(n) t(n) )/ T(n) ?0 ， as n??。 ? t(n)是 T(n)的漸近性態(tài)，為算法的漸近復(fù)雜性。 ? 在數(shù)學(xué)上， t(n)是 T(n)的漸近表達式，是 T(n)略去低階項留下的主項。它比 T(n) 簡單。
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1