我有一个算法,我发现它的运行时复杂度遵循以下公式:
[log(1)]^2 + [log(2)]^2 + [log(3)]^2 + ....... + [log(n)]^2
log的底数是2
我如何根据这个公式计算出 Θ/Ο 算法的复杂度?
最佳答案
对于上界你可以推理成 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
关于algorithm - 如何计算对数系列的平方和,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/19150268/