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

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