[理工] 資結時間複雜度的T or F QaOe PTT批踢踢實業坊

作者: QaOe (暱稱肥宅) 2018-07-04 14:47:22

https://i.imgur.com/zU0Kiil.jpg
這題我手邊的答案是給T
但是不太懂如果是T的話
那C和n_0要怎麼找
不知道是我抄錯還是哪裡理解錯誤

作者: EXPCDR (EXPCDR) 2018-07-06 08:46:00

我覺得我想的方式是錯的，等看有沒有人知道第八題了

作者: alan23273850 2018-07-06 02:57:00

換我不太懂七跟八差在哪

作者: EXPCDR (EXPCDR) 2018-07-05 22:42:00

是T沒錯左邊是對數等級而已我找c跟n0不像樓上那麼專業，都是直接找看起來就有符合定義的數，下面以d=4為例https://i.imgur.com/MgjoYZg.jpg想請問為什麼第八題會是F哦我知道了因為分母可能變0

作者: alan23273850 2018-07-04 15:55:00

記得這題題幹的c跟big O定義裡面那個c是兩回事你必須先替這題的題幹c找到一個常數k，假設是3好了然後再找另一個常數係數A，計算A*log(n)^3和n的微分去觀察什麼時候log那邊的微分永遠比n那邊小，那這樣門檻值n0就找到了最後你再說 for all k 這個事實都成立即可

作者: eggy1018 (ç¾…å¯†æèˆ‡è±¬éŽå¤œ) 2018-07-06 15:18:00

8,若k=n雙邊取log後,左邊nlog(logn),右邊logn,所以左>右

作者: EXPCDR (EXPCDR) 2018-07-06 22:07:00

那條件設k不等於n才對吧，可是他條件是k>0

作者: eggy1018 (ç¾…å¯†æèˆ‡è±¬éŽå¤œ) 2018-07-07 00:04:00

應該是說這題k並沒有被指定所以沒辦法確定，但是k=n時我認為會有上述情形發生

作者: alan23273850 2018-07-07 16:52:00

所以第八題的 k 是變數就對了

繼續閱讀