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

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 )

为了证明下界，需要证明给定的总和 >= 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