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 种情况都不适用

\n\n

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

\n\n

（对于任意基数，这并不重要）

\n\n

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

\n\n

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

\n\n

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

\n\n

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

\n\n

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

\n\n

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

\n\n

情况 2： f(n)=n log n=\xce\x98(n ¹ log ¹ n) 因此 U(n)=\xce\x98(n log ² n)

\n\n

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

\n\n

情况 2： f(n)=n =\xce\x98(n ¹ log ⁰ n) 因此 L(n)=\xce\x98(n log n)

\n\n

因为L(n)<=T(n)<=U(n)它遵循 T(n)=O(n log ² n) 且 T(n)=\xce\xa9(n log n)

\n\n

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

\n