Lv,Gucci,Lv包包,Lv錢夾,Lv手錶,Lv目錄,Gucci公仔包,Lv購物包,Lv水桶包,Lv批發,LV333名牌購物Lv,Gucci,Lv包包,Lv錢夾,Lv手錶,Lv目錄,Gucci公仔包,Lv購物包,Lv水桶包,Lv批發,LV333名牌購物Lv,Gucci,Lv包包,Lv錢夾,Lv手錶,Lv目錄,Gucci公仔包,Lv購物包,Lv水桶包,Lv批發,LV333名牌購物Lv,Gucci,Lv包包,Lv錢夾,Lv手錶,Lv目錄,Gucci公仔包,Lv購物包,Lv水桶包,Lv批發,LV333名牌購物

1.
f(n) 兩項 (n^2 + n log n)^2, (log n + 1)(n^2 + n^3) 加總

n^2 成長大於 n log n, 因此 n^2 + n log n = O(n^2)

(n^2 + n log n)^2 → O(n^4)

(log n + 1)(n^2 + n^3) 對兩括號取 O, O(log n) 和 O(n^3)

(log n + 1)(n^2 + n^3) → O(n^3 log n)

f(n) = O(n^4) + O(n^3 log n), 仍須比兩項成長

n 成長大於 log n, 故 n^4 成長大於 n^3 log n

f(n) = O(n^4)

2. 註:共有的 x>=x0 不贅述
(1)
f(x)=o(g(x)) → f(x)<=c1g(x) for some positive constant c1

f(x)=o(g(x)) → f(x)<c2g(x) for all positive constant c2

f(x)=o(g(x)), 則每個 c2 都滿足 O 定義的 c1, 選項正確

(2)
f(x)=O(g(x)) → 定義的 f(x)<=c1g(x) → g(x)>= (1/c1) f(x)

存在 1/c1 滿足 Ω 定義,選項正確

(3)
Θ 是 tight bound, O 和 Ω 同時被滿足,選項正確

(4)
令 f(x)=g(x)=x, 則 Θ 關係明顯成立

但 o 定義的常數無法是「任意正常數」

如 x<c2x 只建立在 c2>1, 不滿足原始定義 for all positive constant

故此選項錯誤

3. 註:省略冗長的証明,只列出結果
a)
決定項為 n^3 log n, 比 n^3 多出 log n 成長,為 Ω(n^3)

b) 同理,為 Ω(n^3)

c)
  lim(n→∞) (log n)^2/n^5
= lim(n→∞) 2(log n)/5n^5
= lim(n→∞) 2/5n^6
= 0

因此 f(n) 決定項為 n^5, n^5=Ω(n^3)

d)
  lim(n→∞) (log n)^5/3n^3
= lim(n→∞) 5(log n)^4/9n^3
  ...
= 0

因此 f(n) 決定項為 n^3, f(n)=Θ(n^3)

Θ 同時也滿足 O, Ω

e)
n^5 + n^3 + 1 = (n^3 + 1)(n^2 + 1) - n^2

f(n) = n^2 + 1 - n^2/(n^3 + 1)

後項為倒數比 1 還小,因此決定項 n^2 = o(n^3)

同時也滿足 O(n^3)

f)
分子次數比分母低,比 1 還小,故屬於 O(n^3) 和 o(n^3)

4.
  T(243)
= 3T(81) + 2*243
= 3( 3T(27) + 2*81) + 2*243
= ...
= 3( 3( 3( 3( 3T(1) + 2*3 ) + 2*9 ) + 2*27 ) + 2*81) + 2*243
= 3( 3( 3( 3( 3*2 + 2*3 ) + 2*9 ) + 2*27 ) + 2*81) + 2*243
= 2916

  T(n)
= 4T(n/3)
= 16T(n/9)
= ...
= 4^k T(n/3^k)
= ...
= 4^m T(1), n=3^m

m=log3(n), T(1)=1 代入得

T(n) = 4^(log3(n)) = n^(log3(4)), log3(4) 約為 1.26186, 介於 n~n^2 間

5.
n 需要 T(n) 處理

10 個 n/3 需要 10T(n/3), 分割合併需要 n^2

因此 T(n) = 10T(n/3) + n^2

6. 註:建議查課本或網頁

泡沫排序法:最佳 O(n), 平均與最差 O(n^2)

交換排序法三種均 O(n^2), 因為一定要從頭比到尾

插入排序法和泡沫相同

7.
標準矩陣乘法:

// C=A*B; A, B, C 維度各為 m*n, n*p, m*p
for (1<=i<=m)
    for (1<=j<=p)
        tmp=0
        for (1<=k<=n)
            tmp+= Aik * Bkj // 乘法
        Cij = tmp

共需執行 m*n*p 次 tmp+= Aik * Bkj, 因此答案 20*20*20=8000

8.
前四大為 n^n, n!, e^n, 2^n

接著 3n^2+5n, = Θ(n^2)

次之 log n! 其實是 Θ(n log n)

再次之 n^0.5, 可用 lim 像前幾題般證明之

最後依序 (log n)^2 與 ln n = Θ(log n)

希望如上回答對您有幫助!

參考資料 Lv,Gucci,Lv包包,Lv錢夾,Lv手錶,Lv目錄,Gucci公仔包,Lv購物包,Lv水桶包,Lv批發,LV333名牌購物Lv,Gucci,Lv包包,Lv錢夾,Lv手錶,Lv目錄,Gucci公仔包,Lv購物包,Lv水桶包,Lv批發,LV333名牌購物Lv,Gucci,Lv包包,Lv錢夾,Lv手錶,Lv目錄,Gucci公仔包,Lv購物包,Lv水桶包,Lv批發,LV333名牌購物Lv,Gucci,Lv包包,Lv錢夾,Lv手錶,Lv目錄,Gucci公仔包,Lv購物包,Lv水桶包,Lv批發,LV333名牌購物
arrow
arrow
    全站熱搜

    collin37 發表在 痞客邦 留言(0) 人氣()