[理工] Substitution Method 問題

[cloudmaster9 (cloudmaster990214)]

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
→ jacksoncsie: 沒辦法一眼就看出是指 (nlgn)^2 ?
(n^2)logn
→ jacksoncsie: 沒辦法一眼就看出是指 (nlgn)^2?
→ jacksoncsie: 用master theroem可以看出前式是n^2 跟後者差lgn
嗯嗯這裡我明白～ 我是指後面n^2logn
※ 編輯: cloudmaster9 (111.83.215.140 臺灣), 11/04/2021 20:10:10
→ jacksoncsie: 所以取後者n^2lgn多乘lgn變成(nlgn)^2
※ 編輯: cloudmaster9 (111.83.215.140 臺灣), 11/04/2021 20:12:31
推 jacksoncsie: 8c感覺跟 4T(n/2) 有關 應該是因前者用c(nlgn)^2
→ jacksoncsie: 所以後者 n^2lgn 享用同係數c才變成8c
→ jacksoncsie: 不過我看又些證明沒有8cn^2lgn那個 可能可以省略?
→ jacksoncsie: 其實可以省 算出來跟答案一樣 = =
→ jacksoncsie: https://i.imgur.com/sqM32ze.jpg
推 jacksoncsie: 等一下 我好像算錯了 不過我真的認為可以省
嗯嗯～ 就是把 -2cn^2logn 排除 大致上就沒問題了
→ jacksoncsie: Stanford 舉的這例子也沒多項
→ jacksoncsie: https://reurl.cc/mv7D4j
→ jacksoncsie: 不過這是算 big O的 big omega應該也同理
謝謝你的回覆
※ 編輯: cloudmaster9 (111.83.215.140 臺灣), 11/04/2021 22:59:01
※ 編輯: cloudmaster9 (111.83.215.140 臺灣), 11/04/2021 22:59:37
推 j12345453: 我昨天也對這題有疑問
推 j12345453: 所以在算這種Substitute 的式子
→ j12345453: 我們有什麼詳細的方法嗎
→ j12345453: 到底後面何時該加什麼
→ j12345453: 何時該多加上N^2logN