專升本計算機導論ppt課件(編輯修改稿)
2025-06-01 18:37 本頁面
【文章內容簡介】 c、 d中各含一個整數。求 a、b、 c中的最大值與 d的乘積。 算法 max1: void max1(int a, b, c, d) { int x。 a*=d。 b*=d。 c*=d。 if (ab) x=a。 else x=b。 if (cx) x=c。 printf(“%d\n”,x) } 算法 max2: void max2(int a, b, c, d) { int x。 if (ab) x=a。 else x=b。 if (cx) x=c。 x*=d。 printf(“%d\n”,x) } 27 算法復雜性的度量 (事例 ) ? 設輸入為： a= b= c= d=4。兩個算法在給定輸入條件下的計算量 乘法 賦值語句 條件語句 max1 3 5 2 max2 1 3 2 若以賦值語句為標準操作，算法 max1和 max2在輸入（ 3， 2， 1， 4）下的計算量為 4和 2。最壞情況下的時間復雜性分別為 5和 3。 28 算法復雜性的度量 (事例 ) ? 例（算法復雜性是問題規(guī)模的函數）：矩陣乘法 void matrimlt(int A[n][n], B[n][n], C[n][n]) /* 求 n階矩陣 A， B的乘積 C*/ { for (i=0。in。i++) for (j=0。 jn。j++) { C[i][j]=0。 /* 執(zhí)行 n2次 */ for(k=0。kn。k++) C[i][j]=A[i][k]*B[k][j]。 /* 執(zhí)行 n3次 */ } } T(n)=n3+n2 29 算法復雜性的漸近性態(tài) ? 設 T（ n）為關于算法 A的復雜性函數。通常， 當 n單調增加且趨于 ∞ 時， T（ n）也單調增加且趨于 ∞ 。 若存在 使得當 n→ ∞ 時有 ～ T（ n） ～ T（ n） T（ n） T（ n） 0 ，則稱 ～ T（ n） 是 T（ n）當 n→ ∞ 時的漸近性態(tài)，或稱 是算法 A當 n→ ∞ 時的漸近復雜性 30 算法復雜性的漸近性態(tài) ? 如當 T（ n） =3n2+4nlogn+7時， ～ T（ n） ～ T（ n） T（ n） T（ n） =0 的一個答案是 3n2 lim n→ ∞ lim n→ ∞ 4nlogn+7 3n2+4nlogn+7 = 為了簡化分析，我們假設算法中用到的所有不同的元運算各執(zhí)行一次所需的時間都是一個單位時間。 只要考慮當問題規(guī)模充分大時，算法復雜性在漸近意義下的階。 31 算法復雜性的漸近性態(tài) ? 設： f(n)和 g(n)是定義在正數集上的正函數。 ? 如果存在正的常數 c和自然數 n0，使得當 n≥ n0時有 f(n) ≤ cg(n)，則稱函數 f(n)當 n充分大時上有界，且 g(n)是它的一個上界，記為 f(n)=O(g(n))。這時還說 f(n)的階不高于 g(n)的階。 ? 例子： ?
教學課件相關推薦
鄂ICP備17016276號-1