algorithm - 如何计算对数系列的平方和

Question

我有一个算法，我发现它的运行时复杂度遵循以下公式:

[log(1)]^2 + [log(2)]^2 + [log(3)]^2 + ....... + [log(n)]^2

log的底数是2

我如何根据这个公式计算出 Θ/Ο 算法的复杂度？

Answer 1

对于上界你可以推理成 log(n!) = O(nlog(n))

[log(1)]^2 + [log(2)]^2 + [log(3)]^2 + ....... + [log(n)]^2 < [log(n)]^2 + ... + [log(n)]^2
                                                            = n[log(n)]^2

[log(1)]^2 + [log(2)]^2 + [log(3)]^2 + ....... + [log(n)]^2  = O( n[log(n)]^2 )

要证明下界，需要证明给定的总和 >= n[log(n)]^2 的常数倍数

从总和中删除前半部分

[log(1)]^2 + [log(2)]^2 + [log(3)]^2 + ....... + [log(n)]^2 >= [log(n/2)]^2 + [log(n/2 + 1)]^2 + [log(3)]^2 + ....... + [log(n)]^2

用 log(n/2) ^ 2 替换每一项

[log(1)]^2 + [log(2)]^2 + [log(3)]^2 + ....... + [log(n)]^2  >= (n/2) * [log(n/2)]^2

下限 = (n/2) * [log(n) - 1] ^ 2

我们可以证明 log(n) - 1 >= (1/2) * log(n)

因此下限 = (n/8) * [log(n)] ^ 2 和上限 = n * [log(n)] ^ 2

所以 Θ([log(1)]^2 + [log(2)]^2 + [log(3)]^2 + ...... + [log(n)] ^2) = n * [log(n)] ^ 2