作者LPH66 ((short)(-15074))
看板Prob_Solve
标题Re: [问题] 请问c(m,n)的asymptotic是多少 @@>?
时间Sat Nov 22 02:24:43 2008
※ 引述《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
1F：推 FRAXIS:原Po问的是算C(m,n)所需要的时间 还是C(m,n)数字的近似? 11/22 08:21
2F：推 ledia:後者 11/22 10:43
3F：推 pigalan:可以用stirling fomula估计吗?(估计n!的那个~) 11/23 13:31
4F：推 ledia:我也想过 stirling, 不过不能确定准不准 11/25 13:33
5F：→ ledia:(直接除的话) 11/25 13:33