复杂度 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)，c∈N。

- oRookie

---

“(log n)^2” 与 “n” 完全不同。 - rici

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

- Bernhard Barker

---

所有的等式都是精确的，但有一个例外，即当 log n 为奇数时，(n * n * n * ...) 实际上等于 (n^{(log n - 1)/2})，如果 log n 为偶数，则等于 (n^{(log n)/2} / n)。 - Dima Chubarov

Answer 2

从一些基本的算术开始：

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

常量可以被忽略。因此：

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

所以，你正在添加一些O(log n)的东西。有多少？大约是log(n)个。这意味着算法是：

O( (log n)^2)

- Gordon Linoff

---

好的，我的想法“大约是log(n)*O(log(n)) = O(n)”是正确的。我猜我需要找另一个算法了。无论如何，谢谢你。 - oRookie

难道不应该是 O(log n/2) = O( (log n) - (log 2)) 吗？同时，被减去的项不是常数——log 2、log 4、log 8 等都会随着 n 的增长而变大。 - Bernhard Barker

你不能忽略无限个（增长的）常数项（实际上不是常数... 你所忽略的这些项实际上也可以加起来得到O((log(n))^2)，所以你在忽略它们时只是碰巧得到了正确的答案... - gdelab

@gdelab . . . 对于任何常数，O(n / C) = O(n)。这不是“运气”，而是复杂度的定义。关键在于项数，而不是每个项的复杂度。 - Gordon Linoff

是的，但是在这里，如果您正确计算，最终会得到 log(n)*log(n)+(log(1/2)+log(1/4)+...+log(1/n))。第二部分不是一个常数，也不能像您建议的那样轻易地忽略它：它是一个具有 Omega(log(n)) 项的总和，其中一些大小为 Omega(log(n))。它们的总和实际上是 Theta((log(n))^2) 的大小。您不能像您正在做的那样逐个忽略该总和中的所有元素！请参见 @Dukeling 的答案以获得更好的计算（尽管仍然不是100％严格的，使用“...”而不是求和/乘法符号）。 - gdelab