作者cloudmaster9 (cloudmaster990214)
看板Grad-ProbAsk
標題[理工] Substitution Method 問題
時間Thu Nov 4 11:48:47 2021
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://webptt.com/m.aspx?n=bbs/Grad-ProbAsk/M.1635997729.A.9EC.html
1F：→ jacksoncsie: 沒辦法一眼就看出是指 (nlgn)^2 ? 11/04 20:07
(n^2)logn
2F：→ jacksoncsie: 沒辦法一眼就看出是指 (nlgn)^2? 11/04 20:08
3F：→ jacksoncsie: 用master theroem可以看出前式是n^2 跟後者差lgn 11/04 20:09
嗯嗯這裡我明白～ 我是指後面n^2logn
※ 編輯: cloudmaster9 (111.83.215.140 臺灣), 11/04/2021 20:10:10
4F：→ jacksoncsie: 所以取後者n^2lgn多乘lgn變成(nlgn)^2 11/04 20:10
※ 編輯: cloudmaster9 (111.83.215.140 臺灣), 11/04/2021 20:12:31
5F：推 jacksoncsie: 8c感覺跟 4T(n/2) 有關 應該是因前者用c(nlgn)^2 11/04 20:16
6F：→ jacksoncsie: 所以後者 n^2lgn 享用同係數c才變成8c 11/04 20:17
7F：→ jacksoncsie: 不過我看又些證明沒有8cn^2lgn那個 可能可以省略? 11/04 20:26
8F：→ jacksoncsie: 其實可以省 算出來跟答案一樣 = = 11/04 20:30
10F：推 jacksoncsie: 等一下 我好像算錯了 不過我真的認為可以省 11/04 20:36
嗯嗯～ 就是把 -2cn^2logn 排除 大致上就沒問題了
11F：→ jacksoncsie: Stanford 舉的這例子也沒多項 11/04 20:37
13F：→ jacksoncsie: 不過這是算 big O的 big omega應該也同理 11/04 20:39
謝謝你的回覆
※ 編輯: cloudmaster9 (111.83.215.140 臺灣), 11/04/2021 22:59:01
※ 編輯: cloudmaster9 (111.83.215.140 臺灣), 11/04/2021 22:59:37
14F：推 j12345453: 我昨天也對這題有疑問 12/11 13:08
15F：推 j12345453: 所以在算這種Substitute 的式子 12/11 14:33
16F：→ j12345453: 我們有什麼詳細的方法嗎 12/11 14:33
17F：→ j12345453: 到底後面何時該加什麼 12/11 14:33
18F：→ j12345453: 何時該多加上N^2logN 12/11 14:33