如何计算对数级数的平方和

Question

我有一个算法，并且我已经计算出它的运行时复杂性遵循以下公式：

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

原木底座为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 )

要证明下界，需要证明给定和是nlog(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