[理工] 資工 演算法 substitution

看板Grad-ProbAsk作者 (阿渝)時間6年前 (2017/12/03 21:33), 編輯推噓1(1推 0噓 6→)
留言7則, 2人參與, 6年前最新討論串1/1
https://i.imgur.com/OFAiFKv.jpg
大概知道substitution就是觀察猜測bound然後證明 有點不太理解為甚麼證明過程要寫那個假設？ 是什麼概念？ 麻煩各位了 -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 223.138.83.18 ※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1512308005.A.097.html
→
12/03 21:36, 6年前 , 1F
把他當作數學歸納法 可式base在這裡是trival的不用證
12/03 21:36, 1F
→
12/03 21:37, 6年前 , 2F
base是trival的 因為只要C夠大就能夠讓base成立
12/03 21:37, 2F
→
12/03 21:41, 6年前 , 3F
打錯字Trivial
12/03 21:41, 3F
→
12/03 21:42, 6年前 , 4F
substitution其實很麻煩印為你假設小於cn最後就定要是
12/03 21:42, 4F
→
12/03 21:43, 6年前 , 5F
小於cn,而不是什麼常數被的cn加上什麼log 一定要是cn
12/03 21:43, 5F
→
12/03 21:44, 6年前 , 6F
所以倒數第二行的證明也是努力湊到讓他小於等於cn
12/03 21:44, 6F
推
12/03 22:38, 6年前 , 7F
強數學歸納法
12/03 22:38, 7F
‣ 更多 jch660tw 的文章
文章代碼(AID): #1Q8_qb2N (Grad-ProbAsk)