[理工] 演算法 時間複雜度 多題

作者: sdfg014025xx (隨便就好)   2018-12-05 12:03:30
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是為什麼?
感謝各位
作者: cossetannie   2018-12-05 12:11:00
前面有人問過了 標題跟你一樣 去看看吧
作者: wei12f8158 (WEI)   2018-12-05 14:02:00
第一題因爲問的是時間複雜度,所以可以想成T(1,1)=T(n,n),T(1,2)=T(n-1,n)...T(1,n-1)=T(2,n),等號左右邊的式子算起來一樣複雜,所以可以化簡成接下來的樣子
作者: eatagary (gary)   2018-12-05 23:24:00
第三題 如果guess cnlogn 算到後面會發現,guess 錯誤,需用-dn,主要是 配合 substitution 方法不矛盾的經驗假設法。
作者: skyHuan (Huan)   2018-12-06 00:03:00
竟然連題目都一樣XDD#1S0w9rvt (Grad-ProbAsk)

Links booklink

Contact Us: admin [ a t ] ucptt.com