在FRAXIS提供的文件中
https://goo.gl/t5ZSz6
p.2
"Theorem 1.
1.
if f(n) = O(n^(lg_b a) / lg n)(1+ε)
for some constant ε > 0,
then T(n) = Θ(n^(lg_b a)).
...
4.
if f(n) = Θ(n^(lg_b a) / lg n),
then T(n) = Θ(f(n) * lg n * lglg n)."
其中 f(n) = O(n^(lg_b a) / lg n)(1+ε)
上面这句是什么意思?
若其意义等于 f(n) = O(n^(lg_b a) / lg n)
那1与4不就矛盾了?
因为若f(n)符合4的条件，则也会符合1的条件。
但是1与4算出的T(n)却不同。
或者是1打错了
应为 f(n) = O( n^(lg_b a) / (lg n)^(1+ε) ) ?