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