[理工] 資結 時間複雜度的T or F

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