作者QaOe (暱稱肥宅)
看板Grad-ProbAsk
標題[理工] 資結 時間複雜度的T or F
時間Wed Jul 4 14:47:22 2018
https://i.imgur.com/zU0Kiil.jpg
這題我手邊的答案是給T
但是不太懂如果是T的話
那C和n_0要怎麼找
不知道是我抄錯還是哪裡理解錯誤
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 39.10.195.121
※ 文章網址: https://webptt.com/m.aspx?n=bbs/Grad-ProbAsk/M.1530686845.A.C40.html
1F：推 alan23273850: 記得這題題幹的c跟big O定義裡面那個c是兩回事 07/04 15:55
2F：→ alan23273850: 你必須先替這題的題幹c找到一個常數k，假設是3好了 07/04 15:57
3F：→ alan23273850: 然後再找另一個常數係數A，計算A*log(n)^3和n的微分 07/04 16:00
4F：→ alan23273850: 去觀察什麼時候log那邊的微分永遠比n那邊小，那這樣 07/04 16:00
5F：→ alan23273850: 門檻值n0就找到了 07/04 16:00
6F：→ alan23273850: 最後你再說 for all k 這個事實都成立即可 07/04 16:01
7F：推 EXPCDR: 是T沒錯 左邊是對數等級而已 07/05 22:42
8F：→ EXPCDR: 我找c跟n0不像樓上那麼專業，都是直接找看起來就有符合定 07/05 22:42
9F：→ EXPCDR: 義的數，下面以d=4為例 07/05 22:42
11F：推 EXPCDR: 想請問為什麼第八題會是F 07/05 22:47
12F：→ EXPCDR: 哦我知道了 因為分母可能變0 07/05 23:32
13F：推 alan23273850: 換我不太懂七跟八差在哪 07/06 02:57
14F：推 EXPCDR: 我覺得我想的方式是錯的，等看有沒有人知道第八題了 07/06 08:46
15F：推 eggy1018: 8,若k=n雙邊取log後,左邊nlog(logn),右邊logn,所以左>右 07/06 15:18
16F：推 EXPCDR: 那條件設k不等於n才對吧，可是他條件是k>0 07/06 22:07
17F：推 eggy1018: 應該是說這題k並沒有被指定所以沒辦法確定，但是k=n時 07/07 00:04
18F：→ eggy1018: 我認為會有上述情形發生 07/07 00:04
19F：→ alan23273850: 所以第八題的 k 是變數就對了 07/07 16:52