[商管] [資結] 99中山資管乙組

[iamhebe ( bbb)]

4.
  Merge-Sort(A,p,r)
  If p < r
     Then q <- └(p+q)/2┘ //flooring
         Merge-Sort(A,p,q)
         Merge-Sort(A,q+1,r)
         Merge(A,p,q,r)

(A)List the recurrence function for the complexity of Merge-Sort(A,1,n)

我是這樣想的
T(n) = T(n/2) + T(n/2) + n
then T(n) = 2T(n/2) + n
不知道這題的遞迴關係是長這個樣子嗎？

7.Consider b identical bins.
(A) Suppose you toss n balls. How many balls fall in a given bin in average?
這題題目只看得懂前面
考慮b個相同箱子，假設你投(放)n個球。
但How many那句我看不懂
是問說一個箱子平均幾個球嗎？
是的話，答案是n/b?


--
※ 發信站: 批踢踢實業坊(ptt.cc) 
◆ From: 111.248.216.204
→ privatewind:(A)的話 我會寫2T(n/2)+O(n)
→ privatewind:不過我覺得你寫那樣也不會差到哪去XD
→ privatewind:只是我表達的 比較模糊一點
→ iamhebe:感謝樓上 那需要寫推導過程嗎 因為這題配分有10分耶
→ iamhebe:還是List的意思是只要列出式子就可以
→ privatewind:7我也覺得是這樣XD
→ iamhebe:恩恩 哈 算習慣排列組合 很不習慣題目長成這樣XD
推 rnbjacky:T(n) = 2T(n/2)+日(n) 後面n加個常數c 變cn 可能比較好唷
→ rnbjacky:7 好像load factor喔  應該是n/b吧..QQ
→ rnbjacky:遞迴在多個初始項 T(n) = 日(1)  if n = 1
→ rnbjacky:T(n) = 2T(n/2) + 日(n) if n > 1  這樣10分可能拿的踏實
→ iamhebe:所以是T(n) = 2T(n/2)+θ(cn)還是c*θ(n)
→ rnbjacky:都不是 是 c*n  日(n) 就可以表達cn了 好像沒有用asymp.
→ rnbjacky:notation　又加常數的　一般應該不會吧..
→ iamhebe:恩恩...了解  太感謝您了:)
→ rnbjacky:因為這個遞迴在原文書上是一個很重要的intro. ！！
→ iamhebe:哈 難怪  我都只看洪兔的講義=w=
推 rnbjacky:應該夠啦　他該教的都有教呢！
→ FRAXIS:7b  #1DAI2cA5
→ sneak: ) https://daxiv.com