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)
希望如上回答對您有幫助!
- Apr 11 Fri 2014 01:06
請教各位有關"演算法"的題目? (20點)
全站熱搜
留言列表