推 amidofun:我用master method T(n)=θ(n) 理論上 應該可以寫T吧 03/23 17:35
推 assassin88:我覺得是 false 03/23 17:36
→ flyguava:參考的答案是false 但我也覺得可以選T 耶 03/23 17:40
→ flyguava:不知道as 大有什麼看法 ?? 謝 03/23 17:40
→ assassin88:不可能是 true 因為 θ 要同時滿足 O & Ω 03/23 17:41
→ assassin88:以定義而言，n 的成長曲線不會大於 nlogn 03/23 17:41
→ assassin88: 等於 03/23 17:42
推 w8formePlz:但是題目是 big O為什麼false? 03/23 17:42
→ flyguava:喔喔喔 還要這樣反向思考 謝了^^ 03/23 17:43
→ w8formePlz:題目不是θ也不行嗎@@?? 03/23 17:44
→ flyguava:w8 大的想法應該跟我一樣，現在也疑惑中了~~ 03/23 17:45
→ assassin88:因為他的 f(n) = cn 並不是θ(n) 03/23 17:45
→ flyguava:順便問政大備100左右有沒有機會啊??? 03/23 17:45
→ assassin88:根據定義 c 為 正整數 所以若 c 取 n 則複雜度為 n^2 03/23 17:46
推 shortoneal:Q sort的best case證明結果就是就是這個欸，為何F啊@@ 03/23 17:46
→ assassin88:Quick sort best case 是 T(n) = 2T(n) + cn = = 03/23 17:47
→ assassin88:少打/2 03/23 17:47
推 shortoneal:best case不是剛好分一半一半，那應該是T(n/2)吧?@@ 03/23 17:49
→ shortoneal:喔喔喔對= = 這樣瞭了 03/23 17:49
→ assassin88:恰分為左右沒錯但左右皆要分批遞迴..建議你在翻翻書XD 03/23 17:50
→ amidofun:我覺得c沒說清楚講明白XDS 03/23 17:52
→ shortoneal:請問C不是只能取定值嗎@@，可以用c=n喔? 03/23 17:52
→ flyguava:我也覺得不行耶.. 03/23 17:53
→ shortoneal:那這樣c如果取了n^100這種東西，不就找不到big O了@@ 03/23 17:53
→ assassin88:沒錯 但根據定義是 c 為正整數 所若前方沒有θ則為 F 03/23 17:53
→ assassin88:若有則為 T，所以一般看到的題目若是 cn 通常會加θ 03/23 17:54
→ assassin88:就是這個原因。 03/23 17:54
→ flyguava:他的下一小題是T(n) = T(n/2)+clogn thenT(n)=O(log^2n) 03/23 17:55
→ amidofun:我常看到c is positive constant 03/23 17:55
→ flyguava:這樣C 取n 的話也變 F了 03/23 17:55
→ amidofun:原來如此 03/23 17:56
→ flyguava:了解^^ 謝了 03/23 17:57
推 FRAXIS:一般會說c是一個常數.. 也就是與n無關 所以應該是T吧 03/23 23:10
→ FRAXIS:原來有人解釋了.. 03/23 23:10