作者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