作者mistel (Mistel)
看板Grad-ProbAsk
標題[理工] 演算法 時間複雜度一題
時間Sat Aug 24 18:13:52 2019
題目
https://i.imgur.com/2jTpAto.jpg
我的過程
https://i.imgur.com/VPv4WaT.jpg
我想確認一下我的過程可以嗎？我是順著寫，歸納假設沒有特別修改，最後的兩個兩行跟老
師的最後兩行是一模一樣的
但是老師有設嚴格的歸納假設，我的問題是為什麼老師要這樣設？看這題沒有必要這樣設
啊@@
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 223.136.150.143 (臺灣)
※ 文章網址: https://webptt.com/m.aspx?n=bbs/Grad-ProbAsk/M.1566641634.A.31B.html
※ 編輯: mistel (223.136.150.143 臺灣), 08/24/2019 18:15:40
1F：推 mi981027: 第一個你的claim那邊 應該是Omega不是big-oh08/24 20:01
2F：→ mi981027: 再來歸納假設那邊，我想要寫<, 不能寫<=08/24 20:01
你說的對，已修正，感謝你！
3F：→ mi981027: 否則就得證明m=n+1的情況了08/24 20:01
4F：→ mi981027: 然後仔細看，詳解在T(n)的第二行就已經套用歸納假設了08/24 20:01
5F：→ mi981027: 其實你的第二行的<=也是用到了歸納假設，只是你的notati08/24 20:01
6F：→ mi981027: on沒有代換成m08/24 20:01
老師上課時是跟我們說之所以演算法不用把notation換成m是因為取足夠大的常數就能自然
得證了，不然其實老師的詳解也是寫了歸納假設後就證明n
課文在這邊有說明
https://i.imgur.com/meJGJ0y.jpg
7F：→ mi981027: 第三行寫反了.. n=m+108/24 20:01
8F：推 mi981027: 第五句是第二行的>=....好多筆誤QQ08/24 20:03
請問mi大，這樣看來我的寫法大致上沒有問題？
我想說老師當初應該也是在解題過程發現無法歸納到欲證才用了比較嚴格的歸納假設，但我
這樣寫下來應該是能夠得到我欲證的東西的
※ 編輯: mistel (223.136.150.143 臺灣), 08/25/2019 00:12:05
※ 編輯: mistel (223.136.150.143 臺灣), 08/25/2019 00:18:32
9F：推 mi981027: 抱歉抱歉@@我看懂你的問題了哈哈08/25 00:59
10F：→ mi981027: 以為你是問為什麼要有歸納假設 08/25 00:59
11F：推 mi981027: 但你的算式有一步導錯了 我想這就是為什麼詳解要這樣設 08/25 01:02
12F：→ mi981027: 歸納假設的原因（為了消掉多出來那項）08/25 01:02
13F：→ mi981027: 所以應該還是要照詳解那樣設吧 08/25 01:02
真的耶QQ感謝你
※ 編輯: mistel (223.136.150.143 臺灣), 08/25/2019 07:53:27