[理工] [資結] 時間複雜度

看板Grad-ProbAsk作者 (賴打葛葛)時間14年前 (2010/03/11 13:20), 編輯推噓5(5推 0噓 5→)
留言10則, 5人參與, 最新討論串2/9 (看更多)
(a)for (a=l; a<=n; a++) for (b=l;b<=a; b*=2) C++; (b)for (a=l; a<=n; a*=2) for (b=l; b<=a; b++) C++; (c)for (a=l; a<=n; a*=2) for (b=l; b<=a; b*=2) C++; 該怎麼求呢? -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 59.121.128.33
推
03/11 13:24, , 1F
連兩題99台科題目 XD
03/11 13:24, 1F
推
03/11 16:11, , 2F
O(nlgn) O((lgn)^2) O(lgnlglgn)
03/11 16:11, 2F
推
03/11 16:58, , 3F
(b)我算 2n-1 (c)我算 (lgn)^2 +lgn...
03/11 16:58, 3F
→
03/11 17:05, , 4F
(c)還要除以2
03/11 17:05, 4F
推
03/11 17:07, , 5F
(b)我也算 2n-1 .. (c)lglgn+lgn-6 .. 這這那那XD
03/11 17:07, 5F
→
03/11 17:07, , 6F
(c) 也補除以二.. EntHeEnd 似乎跟我算的一樣
03/11 17:07, 6F
推
03/11 17:08, , 7F
C應該是O((lg n)^2)
03/11 17:08, 7F
→
03/11 17:09, , 8F
我打錯.. 我的式子 (3+logn)(logn-2) 是 (lgn)^2 沒錯
03/11 17:09, 8F
→
03/11 17:12, , 9F
(c)差一點點 邊界問題
03/11 17:12, 9F
→
03/11 17:14, , 10F
(c)準確一點 好像是 [(lgn+2)lgn]/2
03/11 17:14, 10F
‣ 更多 lightergogo 的文章
文章代碼(AID): #1Bc7sCX4 (Grad-ProbAsk)
討論串 (同標題文章)
完整討論串 (本文為第 2 之 9 篇)：
排序： 最舊先 | 最新先 | 留言數
在新視窗開啟完整討論串 (共9篇)
‣ 更多 lightergogo 的文章
文章代碼(AID): #1Bc7sCX4 (Grad-ProbAsk)