作者waiting93 ()
站內Prob_Solve
標題[問題] 時間複雜度相關問題
時間Thu Jan 7 19:18:03 2010
請問 C(n,1)+C(n,2)+....+C(n,[n/2])的時間複雜度為何??
其中 C(n,1)= n!/[(n-1)!*1!]
而式子中的最後一項 C(n,[n/2])裡的 [n/2] 代表 n/2 取下高斯
ex [7/2]=3
我算出來的答案為 n^(n/2) 不過沒有答案可以對
請板上的高手替我驗證 謝謝
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.113.144.129
1F：推 tkcn:假設乘法為 O(1) 的話，O(n) 就夠了吧 01/07 19:25
2F：推 FRAXIS:你可以用二項式定理算.. 01/07 22:03
3F：推 march20:問題一開始就問錯了. 第一行的式子哪裡有說到時間呢? 01/12 12:45
4F：→ doom8199:O(2^n) 吧 01/16 15:15