[理工] 資工 演算法 substitution

[jch660tw (阿渝)]

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
→ TMDTMD2487: 把他當作數學歸納法 可式base在這裡是trival的不用證
→ TMDTMD2487: base是trival的 因為只要C夠大就能夠讓base成立
→ TMDTMD2487: 打錯字Trivial
→ TMDTMD2487: substitution其實很麻煩印為你假設小於cn最後就定要是
→ TMDTMD2487: 小於cn,而不是什麼常數被的cn加上什麼log 一定要是cn
→ TMDTMD2487: 所以倒數第二行的證明也是努力湊到讓他小於等於cn
推 clonsey1314: 強數學歸納法