[理工] 资料结构时间复杂度 filcogw PTT批踢踢实业坊

楼主: filcogw (filcogw) 2019-08-02 20:24:51

题目：
T(n) = 2T(n/2) + n/lg n
解法：利用展开带入能求出
Ans : O(n*lglgn)
想问利用Master theory 判断出是case1
但为什么不能使用（答案错误

作者: zuchang (chang) 2019-08-02 20:34:00

Extended master theory

作者: tayashot (Taya) 2019-08-03 00:03:00

作者: Faker0613 (月巴月巴) 2019-08-05 16:59:00

你定义没看清楚回去重看MT

作者: AdonisLam (Adonis) 2019-08-06 11:29:00

f(n)=O(n^(logba-ε)),前提是要找的到ε>0且为常数，这个case1找出的ε会跟n有关

作者: frank1688 (frank1688) 2019-08-08 00:10:00

对，此题只能用展开代入，而不能用case1原因再你解出来的不等式为log n >= n^ε（c取1情况下），此情况不可能发生，因为ε要是大于0之常数

继续阅读