algorithm - 算法复杂度，求解递归方程

Question

我正在学习数据结构和算法课程，但我陷入了这个递归方程：

T(n) = logn*T(logn) + n

显然这不能通过使用主定理来处理，所以我想知道是否有人对求解这个递归方程有任何想法。我很确定应该通过更改参数来解决它，例如将 n 视为 2^m ，但我无法找到任何好的解决方法。

Answer 1

这绝不是官方证明，但我认为它是这样的。

关键是+ n部分。因此，T以 为界o(n)。（或者那应该是大欧米茄？我生疏了。）所以让我们假设T(n) = O(n)并尝试一下。

代入原来的关系

T(n) = (log n)O(log n) + n
     = O(log^2(n)) + O(n)
     = O(n)

所以它仍然成立。

Answer 2

答案是Theta(n)。要证明某事是Theta(n)，你必须证明它是Omega(n)和O(n)。 Omega(n)在这种情况下很明显，因为T(n)>=n. 为了证明这一点T(n)=O(n)，首先

1. 选择一个大的有限值N，使得log(n)^2 < n/100所有n>N. 这是可能的，因为log(n)^2=o(n).
2. 选择一个常数C>100，使得T(n)<Cn所有n<=N. 这是可能的，因为它N是有限的。

我们将归纳地证明T(n)<Cn这一点n>N。由于log(n)<n，根据归纳假设，我们有：

T(n) < n + log(n) C log(n) 
     = n + C log(n)^2
     < n + (C/100) n 
     = C * (1/100 + 1/C) * n
     < C/50 * n
     < C*n

事实上，对于这个函数，甚至可以T(n) = n + o(n)使用类似的参数来证明这一点。