作者sdfg014025xx (隨便就好)
看板Grad-ProbAsk
標題[理工] 演算法 時間複雜度 多題
時間Wed Dec 5 12:03:30 2018
1.題目
https://i.imgur.com/rcRtOvI.jpg
https://i.imgur.com/l618qKe.jpg
請問為什麼解答畫線的部分可以直接那樣轉變？
2.
https://i.imgur.com/6lQzokS.jpg
這邊為什麼是變成8c，是單純假設嗎？
3.
https://i.imgur.com/e3JOmrQ.jpg
這邊能設成<=cnlogn嗎？
因為看前面類似的題目都是直接設，但這題多了個減常數倍的n是為什麼？
感謝各位
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 123.194.114.144
※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1543982613.A.36D.html
推 cossetannie: 前面有人問過了 標題跟你一樣 去看看吧 12/05 12:11
推 wei12f8158: 第一題因爲問的是時間複雜度，所以可以想成T(1,1)=T(n 12/05 14:02
→ wei12f8158: ,n)，T(1,2)=T(n-1,n)...T(1,n-1)=T(2,n)，等號左右 12/05 14:02
→ wei12f8158: 邊的式子算起來一樣複雜，所以可以化簡成接下來的樣子 12/05 14:02
推 eatagary: 第三題 如果guess cnlogn 算到後面會發現，guess 錯誤 12/05 23:24
→ eatagary: ，需用-dn,主要是 配合 substitution 方法不矛盾的經驗 12/05 23:24
→ eatagary: 假設法。 12/05 23:24
推 skyHuan: 竟然連題目都一樣XDD 12/06 00:03