看板 [ Grad-ProbAsk ]
討論串[理工] [資結]-時間複雜度
共 38 篇文章
內容預覽： 開啟 | 關閉 | 只限未讀
首頁
上一頁
1
2
3
4
5
6
7
8
下一頁
尾頁
#13
Re: [理工] [資結]-時間複雜度
推噓1(1推 0噓 3→)留言4則，0人參與, 最新作者cormen5566 (怕熱非洲土著)時間16年前 (2009/11/13 16:30), 編輯資訊
0
0
0
內容預覽:
T(n) ≦ T(ceiling(n/5)) + T(7n/10 + 6) + O(n). ≒ T(n/5) + T(7n/10) + O(n). ＝ O(n) (因為n/5 + 7n/10 < n). T(n) ＝ T(n-a)+T(a)+cn. ＝ O(n^2). (n). / \. (n-a)
(還有63個字)
#12
[理工] [資結]-時間複雜度
推噓2(2推 0噓 9→)留言11則，0人參與, 最新作者sssmallwing (奄是涼小赫$__$)時間16年前 (2009/11/12 15:30), 編輯資訊
0
0
0
內容預覽:
T(n)<= T(ceiling(n/5))+T(7n/10 +6)+O(n). T(n)= T(n-a)+T(a)+cn where a>=1 and c>0. 麻煩板上各位前輩!. 感謝大家!!. --. ※ 發信站: 批踢踢實業坊(ptt.cc). ◆ From: 140.113.210.26
#11
[理工] [資結]-時間複雜度
推噓2(2推 0噓 3→)留言5則，0人參與, 最新作者sssmallwing (奄是涼小赫$__$)時間16年前 (2009/10/18 12:36), 編輯資訊
0
0
0
內容預覽:
T(n)=2*T(floor(n/2))+n 要證Φ(nlgn). O(nlgn). T(n) <= 2*T(n/2)+n = O(nlgn). 不知這樣是否可行?. Ω(nlgn). 這要如何證呢?. 現在手邊沒有書，請大家幫忙一下，感謝!. --. ※ 發信站: 批踢踢實業坊(ptt.cc).
#10
Re: [理工] [資結]-時間複雜度
推噓2(2推 0噓 0→)留言2則，0人參與, 最新作者FRAXIS (喔喔)時間16年前 (2009/10/16 23:46), 編輯資訊
0
0
0
內容預覽:
因為j每次都會自己乘自己 也就是 2, 2^2, 2^4, 2^8 ...增加. 如果n = 2^2^k 那 就會需要跑k次迴圈， k = O( lg lg n ). 乘上外層的n 就變成 O( n lg lg n )了. --. ※ 發信站: 批踢踢實業坊(ptt.cc). ◆ From: 140
#9
Re: [理工] [資結]-時間複雜度
推噓2(2推 0噓 0→)留言2則，0人參與, 最新作者nowar100 (拋磚引玉)時間16年前 (2009/10/16 22:46), 編輯資訊
0
0
0
內容預覽:
原文恕刪. 我算的前兩題跟你一樣，可是我覺得是解答的錯 Orz||. 這題列式出來是 T(n) = T(n/2) + Θ(1). 所以答案是 O(lgn). 你被他前面的係數3給騙囉~. --. ※ 發信站: 批踢踢實業坊(ptt.cc). ◆ From: 140.113.93.39.
首頁
上一頁
1
2
3
4
5
6
7
8
下一頁
尾頁