Re: [問題] 請問c(m,n)的asymptotic是多少 @@>?
看板Prob_Solve (計算數學 Problem Solving)作者LPH66 ((short)(-15074))時間16年前 (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
推
11/22 08:21, , 1F
11/22 08:21, 1F
推
11/22 10:43, , 2F
11/22 10:43, 2F
推
11/23 13:31, , 3F
11/23 13:31, 3F
推
11/25 13:33, , 4F
11/25 13:33, 4F
→
11/25 13:33, , 5F
11/25 13:33, 5F
討論串 (同標題文章)
本文引述了以下文章的的內容：
完整討論串 (本文為第 2 之 2 篇)：
Prob_Solve 近期熱門文章
PTT數位生活區 即時熱門文章
