T(n) = 2T(n/2) + n lg lg n 的渐近上界和下界是什么？

Question

这个递归关系式为：

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

(其中lg是以2为底的对数)，可以使用主定理来求解，但我不太确定答案。我已经找到了答案，但为了防止信息级联，我不会在这里提及。请帮我找出上述问题的大O和Ω。

- Programmer

---

@Bart所提到的意思是“不仅要发布结果，还要说明你的推理过程”。不要害怕出错，因为这比懒惰好得多，也不必担心影响他人，因为这里有很多在影响老板和了解行情的冠军。 - Dr. belisarius

猜测nlglgn应该是n * log(log(n))。 - borrible

抱歉表述不够清晰，lg n 表示以 2 为底。此外，我得到了以下结果：大 O（n^2）和 omega 是 nlog（以10为底）n。 - Programmer

推理：nlglgn <= n2。因此，主定理中的k为2。a为2，b为2。由于a<b^k，因此大O为n2。omega也是如此。让我们看看专家们能为我做些什么。请提供推理 :) - Programmer

你们需要更多关于这个问题的信息吗？如果不需要，请投票支持此问题，以便其他人更加关注它。 - Programmer

Answer 1

主定理中的3种情况都不适用于此。

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

(使用任意基数，实际上并不重要)

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

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

- Ishtar