作者filcogw (filcogw)
看板Grad-ProbAsk
标题[理工] 资料结构 时间复杂度
时间Fri Aug 2 20:24:51 2019
题目：
T(n) = 2T(n/2) + n/lg n
解法：利用展开带入能求出
Ans : O(n*lglgn)
想问利用Master theory 判断出 是case1
但为什麽不能使用（答案错误
----
Sent from
BePTT
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 110.50.140.195 (台湾)
※ 文章网址: https://webptt.com/cn.aspx?n=bbs/Grad-ProbAsk/M.1564748693.A.4D3.html
1F：推 zuchang: Extended master theory08/02 20:34
3F：推 Faker0613: 你定义没看清楚 回去重看MT08/05 16:59
4F：→ AdonisLam: f(n)=O(n^(logba-ε)),前提是要找的到ε>0且为常数，这08/06 11:29
5F：→ AdonisLam: 个case1找出的ε会跟n有关08/06 11:29
感谢前面的回达 但这题应该不适用 extended M T吧 只能展开带入（？
※ 编辑: filcogw (1.200.211.95 台湾), 08/06/2019 18:49:02
6F：推 frank1688: 对，此题只能用展开代入，而不能用case1原因再你解出 08/08 00:10
7F：→ frank1688: 来的不等式为log n >= n^ε（c取1情况下） ，此情况不 08/08 00:10
8F：→ frank1688: 可能发生，因为ε要是大於0之常数 08/08 00:10