algorithm - What is the runtime of the following recursive algorithm using the Master Theorem?

Question

I'm not particularly sure about the runtime of the following algorithm:

T(n) = 2T(n/2) + n/logn

I think this would be O(n) by the Master Theorem but I don't know whether n/logn is asymptotically equal to n. Can someone explain it?

Answer 1

考虑 (n/log(n))/n 的极限，因为 n 趋于无穷大。对于所有 n>0，(n/log(n))/n 等于 1/log(n)。1/log(n) 趋于零，因为 n 趋于无穷大，而不是 1，因此 n/log(n) 和 n 不是渐近相等的。

Answer 2

n并且log n不是渐近相等的。如果您尝试lim n / log n在n = inf极限范围内计算，您可以使用L'Hôpital 规则并很快lim n得到无穷大，从而证明它n渐近大于log n。

但是，更大的问题是，根据少数地方，您的问题是病态的。这种情况不满足主定理的先决条件。在示例 7中掠夺。- 正是你的情况。