[理工] Substitution Method 問題

看板Grad-ProbAsk作者 (cloudmaster990214)時間4年前 (2021/11/04 11:48), 4年前編輯推噓4(4推 0噓 14→)
留言18則, 2人參與, 最新討論串1/1
https://i.imgur.com/n29d2Xs.jpg
沒辦法一眼就看出 後面的 8c(n^2)logn 想說先用代數d 做係數再去滿足 再去找合適的條件 不知是否有通用的方法 代數太多自己可能也會亂掉 下方是我想去湊出來的想法 https://i.imgur.com/hVGqORf.jpg
----- Sent from JPTT on my iPhone -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 111.83.215.140 (臺灣) ※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1635997729.A.9EC.html
→
11/04 20:07, 4年前 , 1F
沒辦法一眼就看出是指 (nlgn)^2 ?
11/04 20:07, 1F
(n^2)logn
→
11/04 20:08, 4年前 , 2F
沒辦法一眼就看出是指 (nlgn)^2?
11/04 20:08, 2F
→
11/04 20:09, 4年前 , 3F
用master theroem可以看出前式是n^2 跟後者差lgn
11/04 20:09, 3F
嗯嗯這裡我明白～ 我是指後面n^2logn ※ 編輯: cloudmaster9 (111.83.215.140 臺灣), 11/04/2021 20:10:10
→
11/04 20:10, 4年前 , 4F
所以取後者n^2lgn多乘lgn變成(nlgn)^2
11/04 20:10, 4F
※ 編輯: cloudmaster9 (111.83.215.140 臺灣), 11/04/2021 20:12:31
推
11/04 20:16, 4年前 , 5F
8c感覺跟 4T(n/2) 有關 應該是因前者用c(nlgn)^2
11/04 20:16, 5F
→
11/04 20:17, 4年前 , 6F
所以後者 n^2lgn 享用同係數c才變成8c
11/04 20:17, 6F
→
11/04 20:26, 4年前 , 7F
不過我看又些證明沒有8cn^2lgn那個 可能可以省略?
11/04 20:26, 7F
→
11/04 20:30, 4年前 , 8F
其實可以省 算出來跟答案一樣 = =
11/04 20:30, 8F
→
11/04 20:34, 4年前 , 9F
11/04 20:34, 9F
推
11/04 20:36, 4年前 , 10F
等一下 我好像算錯了 不過我真的認為可以省
11/04 20:36, 10F
嗯嗯～ 就是把 -2cn^2logn 排除 大致上就沒問題了
→
11/04 20:37, 4年前 , 11F
Stanford 舉的這例子也沒多項
11/04 20:37, 11F
→
11/04 20:38, 4年前 , 12F
11/04 20:38, 12F
→
11/04 20:39, 4年前 , 13F
不過這是算 big O的 big omega應該也同理
11/04 20:39, 13F
謝謝你的回覆 ※ 編輯: cloudmaster9 (111.83.215.140 臺灣), 11/04/2021 22:59:01 ※ 編輯: cloudmaster9 (111.83.215.140 臺灣), 11/04/2021 22:59:37
推
12/11 13:08, , 14F
我昨天也對這題有疑問
12/11 13:08, 14F
推
12/11 14:33, , 15F
所以在算這種Substitute 的式子
12/11 14:33, 15F
→
12/11 14:33, , 16F
我們有什麼詳細的方法嗎
12/11 14:33, 16F
→
12/11 14:33, , 17F
到底後面何時該加什麼
12/11 14:33, 17F
→
12/11 14:33, , 18F
何時該多加上N^2logN
12/11 14:33, 18F
‣ 更多 cloudmaster9 的文章
文章代碼(AID): #1XWrWXdi (Grad-ProbAsk)