推 FRAXIS:原Po問的是算C(m,n)所需要的時間 還是C(m,n)數字的近似? 11/22 08:21
推 ledia:後者 11/22 10:43
推 pigalan:可以用stirling fomula估計嗎?(估計n!的那個~) 11/23 13:31
推 ledia:我也想過 stirling, 不過不能確定準不準 11/25 13:33
→ ledia:(直接除的話) 11/25 13:33
※ 引述《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