推 wyrj:不成立 f(n) = n^2 g(n) = n^3 12/28 22:41
推 da0910cc:今天模考也考了類似題XD 12/28 22:42
→ a613204:我看書上98年交大上面寫到polynomaially bounded 12/28 22:43
→ a613204:上面寫用log法得知log f(n) = O(logn) 來看覺得怪怪的 12/28 22:44
推 wyrj:我寫反了QQ 12/28 22:44
推 pikachu123:這個是對的 一樓的例子 log(f(n))=2n log(g(n))=3n 12/28 22:47
→ a613204:請問是書寫錯嗎? 12/28 22:48
→ pikachu123:應該是錯的 等於不行 log取完複雜度一樣不代表原本2個 12/28 22:49
→ pikachu123:一樣大 12/28 22:49
→ pikachu123:小o會對是因為他沒等號 沒想清楚XD 12/28 22:49
→ a613204:那log(f(n))=o(log(g(n))) 保證 f(n) = o(g(n))是對的吧? 12/28 22:50
→ a613204:怎嚜覺得這本小錯誤好像有點多QQ 12/28 22:51
推 pikachu123:用一樓的例子來看就OK了 它們取完log成長是一樣的 12/28 22:54
→ pikachu123:但是原本複雜的並不是同一等級 12/28 22:54
→ a613204:請問polynomially bounded要怎麼要比較好判別呢? 12/28 23:31
推 pikachu123:取完log(f(n))=O(logn) 就是polynomially bounded 12/28 23:32
→ pikachu123:這Cormen的習題 12/28 23:33
→ pikachu123:交大那題是Cormen習題 12/28 23:33
→ a613204:感恩 12/28 23:36
→ a613204:不過我看上面不是寫log耶 是f(n)=O(n^k) 12/28 23:43
推 pikachu123:你取log不就klogn=O(logn) 12/28 23:46
→ a613204:剛剛不是說log(f(n))=O(log(g(n))) 不保證 f(n) = O(g(n)) 12/28 23:48
推 pikachu123:如果他在多項式時間以上 他取log絕不會在O(logn) 12/28 23:51
→ pikachu123:剛剛舉的那個反例 那2個都是多項式時間 12/28 23:53
→ a613204:所以這算是特例嗎? 12/28 23:53
→ pikachu123:多項式時間取完log都在logn等級以下 12/28 23:54
→ a613204:喔~~我大概懂了 謝謝你:) 12/28 23:57