作者oao521 (一样的午後时光)
看板Grad-ProbAsk
标题[理工] 时间复杂度
时间Sun Feb 16 11:18:46 2020
https://i.imgur.com/S9mOpVV.jpg
https://i.imgur.com/h5ghXCj.jpg
请问这一题D选项
只写 a, b are real constants
那...请问
若b为负数时，要怎麽证呢？
答案给D is correct
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 1.200.210.32 (台湾)
※ 文章网址: https://webptt.com/cn.aspx?n=bbs/Grad-ProbAsk/M.1581823128.A.A11.html
1F：推 maple205: 时间复杂度不会是负的 没有演算法会因为output越大 02/16 11:21
我是指b<0的情况
2F：→ maple205: 做得时间反而变少 02/16 11:21
3F：→ oao521: 所以这一题 02/16 11:30
4F：→ oao521: 虽然题目只说b是实数 02/16 11:30
5F：→ oao521: 但是我们要自动假设其实题目只考虑正实数的情况？ 02/16 11:30
6F：→ oao521: 也就是说我们写题目的时候 就先假设前提：题目不考虑b为负 02/16 11:32
7F：→ oao521: 数 02/16 11:32
8F：→ oao521: 这样理解对吗？ 02/16 11:33
9F：→ DLHZ: 在b为负数的情况下 theta内的n^b乘上任一常数在n趋近於无趣 02/16 11:35
10F：→ DLHZ: 大的情况下依然是0 无法得出大於左方函数的部分 我认为要正 02/16 11:35
11F：→ DLHZ: 确应该改成omega或者for some positive constant b 02/16 11:35
12F：→ DLHZ: 修正一下 两者在n够大後都是0 应该是没问题才对 02/16 11:38
考试时需要考虑b<0的情况吗？
那这样也可以说b<0时
(n+a)^b=theta(n^b)亦成立？
证明是用极限limit来证明吗？
※ 编辑: oao521 (1.200.210.32 台湾), 02/16/2020 11:45:14
※ 编辑: oao521 (1.200.210.32 台湾), 02/16/2020 11:46:26
※ 编辑: oao521 (1.200.210.32 台湾), 02/16/2020 11:54:17
13F：→ DLHZ: 基於上面解释的 我认为对啦 至於考试到底怎样就看个人吧 02/16 11:56
14F：→ DLHZ: 用极限说明我是觉得蛮好用的 好像有其他方法 不过我没去读 02/16 11:57
感谢大大的解释：)
※ 编辑: oao521 (1.200.210.32 台湾), 02/16/2020 12:10:30
15F：推 hit5180214: 负的也会成立，当b是正的会被限制在某个范围间，取倒 02/16 12:21
16F：→ hit5180214: 数之後也当然会被bound 住 02/16 12:21
17F：→ hit5180214: b由正转负，系数取倒数就出来了啊 02/16 12:22
18F：推 zuchang: 直接用BigO定义,找出存在一个c来证就好,用极限也很好 02/16 23:59