应用主定理的案例 3
Applying Case 3 Of The Master Theorem
算法介绍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)，但这与上面的说法矛盾。我究竟做错了什么？
IIUC，你对案例3的前提的应用有误
你的复发是
T(n) = 3 T(n/3) + n/lg(n)
其中，在conventions of the Master Theorem中表示a = b = 3
对于 the third case，您必须有 n / log(n) = Ω(nc)，其中 c > log3(3) = 1。这确实不适用于这里。
算法介绍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)，但这与上面的说法矛盾。我究竟做错了什么？
IIUC，你对案例3的前提的应用有误
你的复发是
T(n) = 3 T(n/3) + n/lg(n)
其中，在conventions of the Master Theorem中表示a = b = 3
对于 the third case，您必须有 n / log(n) = Ω(nc)，其中 c > log3(3) = 1。这确实不适用于这里。