algorithm - T(n) = 2T(n/2) + n lg lg n 的渐近上限和下限是多少？

Question

递归关系

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

（其中 lg 是以 2 为底的对数）可以使用主定理解决，但我不太确定答案。我找到了我的答案，但为了防止信息级联，我没有在这里提及。请帮我找到上面的大 O 和 Ω。

Answer 1

主定理中的 3 种情况均不适用

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

（使用任意基数，这并不重要）

情况 1：f(n)=n log(log n) 比 n ^{log2 2} =n ^{1 “大”}

情况2：f(n)不适合n log ^k (n)

情况 3：f(n) 小于 n ^1+e

U(n)=2 U(n/2) + n log n
L(n)=2 L(n/2) + n

你可以证明：U(n) >= T(n)和L(n) <= T(n)。所以 U 给出了 T 的上限，L 给出了 T 的下限。

应用 U(n) 的主定理，给出

情况 2：f(n)=n log n=Θ(n ¹ log ¹ n) 因此 U(n)=Θ(n log ² n)

应用 L(n) 的主定理，给出

情况 2：f(n)=n =Θ(n ¹ log ⁰ n) 因此 L(n)=Θ(n log n)

因为L(n)<=T(n)<=U(n)它遵循 T(n)=O(n log ² n) 和 T(n)=Ω(n log n)

另外，请注意 O(log ₂ n)=O((log n)/log 2)=O((log n) * c)=O(log n)。