以下等式中的大奥

Question

如何求下面方程的上界，谢谢!

2log(mn2)+4log(mn4)+...。+ mlog(mnm)

Answer 1

这笔款项的计算结果是： Θ(m log n).

我们先重写一下

2^k 对数(锰2)^k) = 2^k(log mn - k)

现在，我们有了

Σ_k=1^对数m 2^k (log mn - k)

= Σ_k=1^对数m (2^k log mn - k 2^k)

= log mn Σ_k=1^对数m 2^k - Σ_k=1^对数m k 2^k

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

2m log mn - 2log mn - Σ。_k=1^对数m k 2^k

因此，我们的任务是简化k2的总和。^k 在某个范围内。这是一个 算术几何和. 如果我们把这个和的范围从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对数m - 2m +2

因此，我们的总金额为

2m log mn - 2log mn - Σ。_k=1^对数 k 2^k

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

= 2m对数mn-2log mn-2m对数m+2m-2。

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

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

Θ(m log n).

希望能帮到你