作者yagerbomb (ㄅD)
看板Grad-ProbAsk
标题[理工] 演算法时间复杂度两题
时间Fri Sep 18 03:04:48 2020
https://i.imgur.com/E3kuBpk.jpg
https://i.imgur.com/K6V4IFD.jpg
第一题想问他的逻辑是不是这样：
因为lg*n = 1+lg*(lgn) = Theta(lg*(lgn))
所以lg*n再取log应该要绝对小於lg*(lgn) 也就是 little - oh
第二题下面 sqrt(n) 变 n/3 我知道n够大的时候会对..但为什麽是取1/3 有特别用意吗
-----
Sent from JPTT on my iPhone
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 110.30.136.42 (台湾)
※ 文章网址: https://webptt.com/cn.aspx?n=bbs/Grad-ProbAsk/M.1600369490.A.246.html
1F：推 zuchang: 第一题little-o 那边错 theta定义再看一次 09/18 10:27
我知道你意思 但我最後有在取一个log
2F：→ zuchang: 啊 抱歉 看错题 09/18 10:27
※ 编辑: yagerbomb (140.112.25.2 台湾), 09/18/2020 10:36:40
3F：推 jason35512: 第一题对 第二题放大没问题,感觉是少加n>=9的条件吧 09/23 18:44