作者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/cn.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