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

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 '更大' support>=n1}

情况 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)。