以下等式的Big-O

Question

如何求下式的上界，谢谢！

2log(mn/2) + 4log(mn/4) + ... + mlog(mn/m)

Answer 1

这个总和等于 Θ(m log n)。

让我们从重写开始

2^k log (mn / 2^k) = 2^k(log mn - k)

现在，我们有了总和

Σ_k=1^{log m} 2^k (log mn - k)

= Σ_k=1^{log m} (2^k log mn - k 2^k)

= log mn Σ_k=1^{log m} 2^k - Σ_k=1^{log m} k 2^k

第一个和是几何级数的和。它简化为 2^{1 + log m} - 2 = 2m - 2。这意味着我们剩下

2m log mn - 2log mn - Σ_k=1^{log m} k 2^k

这给我们留下了在一定范围内简化总和 k2^k 的任务。这是一个arithmetico-geometric sum。如果我们想象这个总和的范围是从 2（含）到某个上限 q，那么总和就是 q2^q+1.

(q+1)2^q+1 - 2 + 2(2 - 2^q+1)

= (q+1)2^q+1 - 2 + 4 - 2·2^q+1

= (q - 1)2^q+1 + 2

您可以通过代入不同的 q 值来检查此公式是否正确。

在我们的例子中，q = log m，所以我们想要的总和为

(log m - 1)2^{1 + log m} + 2

= (log m - 1)(2m) + 2

= 2m log m - 2m + 2

所以我们的总和等于

2m log mn - 2log mn - Σ_k=1^{log mn} k 2^k

= 2m log mn - 2log mn - (2m log m - 2m + 2)

= 2m log mn - 2log mn - 2m log m + 2m - 2

= 2m (log mn - log m + 1) - 2log mn - 2

= 2m (log n + 1) - 2 log mn - 2

Θ(m log n).

希望对您有所帮助！