作者jerry771210 (嘿嘿嘿)
看板NTUE-CS100
标题Re: [课业] 3/17 演算法
时间Wed Mar 18 00:05:54 2009
解三题简单的:
a. T (n) = 3T (n/2) + n lg n
We have f (n) = nlgn and ( n^log a) = nlg 3 = n^lg3 ≒ n^1.585
b
Since n lg n = O(n^lg 3-ε) for any 0 < ε≦ 0.58
by case 1 of the master theorem, we have
T(n) = θ(n^lg 3)
-------------------------------------------------------------------
b.T (n) = 4T (n/2) + n^2√n
We have f (n) = n^2(√n) = n^5/2 and n^log a = n^log 4 = n^lg 2.
b 2
Since n^5/2 = Ω(n^lg 2+3/2),
we look at the regularity condition in case 3 of the master theorem.
We have af(n/b) = 4(n/2)^2 (√n/2) = (n^5/2)/(√2) ≦ cn^5/2,for 1/√2 ≦ c < 1
Case 3 applies, and we have
T (n) = θ(n^2 √n)
--------------------------------------------------------------------
g.T(n) = T(n-1) + 1/n
This recurrence corresponds to the harmonic series, so that T (n) = Hn,
where Hn = 1/1+1/2+1/3+· · ·+1/n. For the base case, we have T (1) = 1 = H1.
For the inductive step, we assume that T(n-1) = Hn-1, and we have
T (n) = T (n-1) + 1/n
= Hn-1 + 1/n
= Hn
Since Hn = θ(lgn) by equation,we have that
T(n) = θ(lgn).
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 140.112.5.53
※ 编辑: jerry771210 来自: 140.112.5.53 (03/18 00:13)
※ 编辑: jerry771210 来自: 140.112.5.53 (03/18 00:15)
1F：→ jerry771210:参考用的 03/18 00:15
2F：推 Kellen310: 噢吼吼吼~~参考一下...我都听不清楚他说什嚜ˊˋ 03/18 00:18
3F：推 nash3629:干 还在拼喔 03/18 00:21
4F：→ nash3629:礼拜二晚上是美丽的夜晚ㄋㄟ 03/18 00:21
5F：→ jerry771210:晚点再po f 那题写法有些复杂 03/18 00:28
6F：推 moonlights:吴季衡超拚的 强 =口= 03/18 00:56