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

看板Grad-ProbAsk作者 (隨便就好)時間7年前 (2018/12/05 12:03), 編輯推噓4(4推 0噓 5→)
留言9則, 4人參與, 7年前最新討論串2/2 (看更多)
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
推
12/05 12:11, 7年前 , 1F
前面有人問過了 標題跟你一樣 去看看吧
12/05 12:11, 1F
推
12/05 14:02, 7年前 , 2F
第一題因爲問的是時間複雜度，所以可以想成T(1,1)=T(n
12/05 14:02, 2F
→
12/05 14:02, 7年前 , 3F
,n)，T(1,2)=T(n-1,n)...T(1,n-1)=T(2,n)，等號左右
12/05 14:02, 3F
→
12/05 14:02, 7年前 , 4F
邊的式子算起來一樣複雜，所以可以化簡成接下來的樣子
12/05 14:02, 4F
推
12/05 23:24, 7年前 , 5F
第三題 如果guess cnlogn 算到後面會發現，guess 錯誤
12/05 23:24, 5F
→
12/05 23:24, 7年前 , 6F
，需用-dn,主要是 配合 substitution 方法不矛盾的經驗
12/05 23:24, 6F
→
12/05 23:24, 7年前 , 7F
假設法。
12/05 23:24, 7F
推
12/06 00:03, 7年前 , 8F
竟然連題目都一樣XDD
12/06 00:03, 8F
→
12/06 00:03, 7年前 , 9F
12/06 00:03, 9F
‣ 更多 sdfg014025xx 的文章
文章代碼(AID): #1S1quLDj (Grad-ProbAsk)
‣ 更多 sdfg014025xx 的文章
文章代碼(AID): #1S1quLDj (Grad-ProbAsk)