algorithm - 复杂度是 O(log(n) + log(n/2) + log(n/4) + log(n/8) + ... + log(2)) = O(log(n)) 吗？

Question

作为家庭作业，我被要求在 O(log(n)) 中编写一个算法，我可以计算出我编写的算法的复杂度为 O(log(n) + log(n/2) + log(n/4) + log(n/8) + ... + log(2)).

我认为它是 O(n)，因为它大致是 log(n)*O(log(n)) = O(n)。但我不确定。我知道这里不欢迎作业问题，但我真的不知道还有什么方法可以找出它的复杂性。谷歌搜索对我没有帮助。

指定:n in N and n = pow(2, c), c in N

Answer 1

不，这不是 O(log n)。它是 O((log n)²).

O(log(n) + log(n/2) + log(n/4) + log(n/8) + ... + log(2))
= O(log(n * n/2 * n/4 * n/8 * ... * 2))                    using log multiplication rule
= O(log(n * n * n * ... * n / 2 / 4 / 8 / ... / n))
= O(log(n<sup>log n</sup> / 2 / 4 / 8 / ... / n))
= O(log(n<sup>log n</sup> / (1 * 2 * 4 * 8 * ... * n/4 * n/2 * n))
= O(log(n<sup>log n</sup> / ((1 * n) * (2 * n/2) * (4 * n/4) * ...)    group first and last terms
= O(log(n<sup>log n</sup> / (n * n * n * ...))                         since we grouped terms,
= O(log(n<sup>log n</sup> / n<sup>(log n)/2</sup>)                                      we halved the number of terms
= O(log(n<sup>log n</sup>) - log(n<sup>(log n)/2</sup>))                             log division rule
= O(log n.log n) - ((log n)/2).log n)                      log power rule * 2
= O(log n.log n) - (log n.log n)/2)
= O(log n.log n)/2)
= O((log n)<sup>2</sup>/2)
= O((log n)<sup>2</sup>)                                              big-O doesn't care about constants