algorithm - 主定理的应用案例 3

Question

算法介绍CLRS 4.3 (b) 有问题

T(n) = 3*T(n/3) + n/lg(n)

注意 n^(log a/ log b) = n^(log 3/ log 3) = 1

该书指出，这里不能应用主定理情况 3，因为 n/log (n) 不是多项式更大的，即它渐近小于 n^(k)，其中 k 是任何正常数。

我的问题是：假设 k = 0.1 那么 n/log (n) 总是渐近大于 n^(0.1)，但这与上述说法相矛盾。我究竟做错了什么？

Answer 1

IIUC，你在应用案例3的前件时有一个错误。

你的复发是

T(n) = 3 T(n/3) + n/lg(n)

其中，在主定理的约定中意味着a = b = 3

对于第三种情况，您必须有n / log(n) = Ω(n ^c )，其中c > log ₃ (3) = 1。这确实不适用于这里。