作者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/cn.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