复杂度是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中的n和n= pow(2，c)，N中的c

Answer 1

从一些基本的算术开始：

O(log n/2) = O( (log n) + log(1/2))

可以忽略该常量。因此：

O(log n / 2) = O(log n)

所以，你添加了一堆O(log )的东西。多少?好吧，关于log(n)值。所以，这意味着算法是：

O( (log n)^2)