作者skyHuan (Huan)
看板Grad-ProbAsk
标题资结 时间复杂度(洪逸笔记)
时间Wed Dec 27 02:17:40 2017
看笔记的时候看到这段觉得怪怪的(右下角的最後三个)
https://imgur.com/UpOiges.jpg
如果直接把这些函数取log再比大小，结果应该是这样
https://imgur.com/mjNstRk.jpg
看到笔记有这样的解释(左下角的部分)
https://imgur.com/mDOpcrX.jpg
有点忘记老师那时候上课是怎麽讲的了
跟同学讨论後觉得老师的意思应该是
先比指数再比底数，指数比较大就比较大
所以O(2^(2n))才会大於O(n^n)因为指数部分2n>n
那这样的话O(5^n)又要怎麽比呢
照上面最後一个笔记的图应该是在最上面那层
但O(5^n)应该要大於O(4^n)=O(2^(2n))吧(?)
不知道我的想法在哪里出错了
麻烦版友帮忙解答了，感谢
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 1.163.16.135
※ 文章网址: https://webptt.com/cn.aspx?n=bbs/Grad-ProbAsk/M.1514312263.A.810.html
※ 编辑: skyHuan (1.163.16.135), 12/27/2017 02:20:13
※ 编辑: skyHuan (1.163.16.135), 12/27/2017 02:21:01
1F：推 rycheal: 呃 应该是 2^2^n 和 n^2^n 才对，不是 2^2n12/27 02:28
2F：→ rycheal: 看你笔记的右边，这个等级是”指数又指数”，不是指数等12/27 02:31
3F：→ rycheal: 级（ex. 5^n）12/27 02:31
4F：→ rycheal: 等级的判断是看你未知数n的所在位置12/27 02:32
所以应该是笔记抄错了吗？
我们有在想是不是2^2^n跟2^2n抄错了，後来看第三个图的笔记後才判断应该不是抄错，
笔记左下的左边有取log算，过程看起来不像2^2^n
※ 编辑: skyHuan (1.163.16.135), 12/27/2017 02:39:41
5F：推 rycheal: 你的笔记完全写错12/27 02:45
6F：→ rycheal: 如果照你的写法来比较nlgn和2n的话，结果会是nlgn>2n12/27 02:45
7F：→ rycheal: 事实上，你2^2^n左边的写法应该要写lg2^2^n，解出来是2^n12/27 02:47
8F：→ rycheal: ，这样才会是2^n>nlgn12/27 02:47
9F：推 rycheal: 这样2^2^n的等级才会大於n^n12/27 02:50
看来应该是笔记抄错了
这样原本想的(第二张图)也没问题了
感谢你！！！
※ 编辑: skyHuan (1.163.16.135), 12/27/2017 02:54:38