Re: [問題] 請問c(m,n)的asymptotic是多少 @@>?

看板Prob_Solve作者LPH66 ((short)(-15074))時間15年前 (2008/11/22 02:24)推噓4(4推 0噓 1→)

留言5則, 3人參與討論串2/2 (看更多)

※ 引述《operationcow (香蕉公車)》之銘言： : 小弟我分析一個演算法 : 分析出來的time complexity是C(m,n) : 我想請問若C(m,n) = theta(f(n)) : 則f(n)為?? : 想了很久又找不太到資料 : 感謝大家 <(__)> 組合數的話...給個參考值吧: 組合數學裡的Catalan number http://en.wikipedia.org/wiki/Catalan_number 4^n Catalan(n) = C(2n,n)/(n+1) = O(---------) n^(3/2) 所以 C(2n,n) 大約是 O(4^n/√n) 又C(m,n)≦C(m,floor(m/2)) (這看一看Pascal triangle就看得出來) 所以一個很粗略的估計是 C(m,n) = O(4^(m/2)/√(m/2)) = O(2^m/√m) 當然如果你的n比較不會在m/2附近的話就要看實際上是如何了 (不過既然看你的m,n好像是獨立的話那這應該就是worst case了) 還有因為是組合數下界不好判定 (要看你的n的情況) 所以這裡給出的都是 big-O 而不是 Θ -- [LPH] Oops, your OOP's a problem? 說: 你現在還是看不到狗? ************* 說: 看得到只是他們不會跑就一直呆呆在那邊一直在起點 [LPH] Oops, your OOP's a problem? 說: 你要按"ㄅㄧㄤˋ"它們才會跑啊@@" -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 140.112.250.80

推

FRAXIS

11/22 08:21, , 1^F

11/22 08:21, 1^F

推

ledia

11/22 10:43, , 2^F

11/22 10:43, 2^F

推

pigalan

11/23 13:31, , 3^F

11/23 13:31, 3^F