[理工] [資結]-台大101-電機(丙組)

看板Grad-ProbAsk作者 (Firefighter)時間14年前 (2012/02/23 10:56), 編輯推噓2(2推 0噓 5→)
留言7則, 3人參與, 最新討論串1/1
http://ppt.cc/3Wq8 請問這題複雜度要怎麼看!! 感謝 -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 192.192.13.101
推
02/23 14:14, , 1F
sum_{i=0~n-1}( O(i) + O(i/2) + O(i/4) + ... )
02/23 14:14, 1F
推
02/23 14:16, , 2F
內層迴圈 i(1+1/2+1/4+1/8)...=O(i) 因此外層就是O(n^2)
02/23 14:16, 2F
→
02/23 14:16, , 3F
<= sum_{i=0~n-1}( O(2i) ), by 無窮等比級數
02/23 14:16, 3F
→
02/23 19:19, , 4F
所以是c?
02/23 19:19, 4F
→
02/23 19:34, , 5F
恩
02/23 19:34, 5F
→
02/23 19:39, , 6F
我無言了...
02/23 19:39, 6F
→
02/23 19:39, , 7F
thanks anyway
02/23 19:39, 7F
‣ 更多 dunkjames 的文章
文章代碼(AID): #1FHQho4E (Grad-ProbAsk)