对数函数求和的复杂度是什么？

Question

我有一个算法，其时间复杂度的大O表示法如下：

log(N) + log(N+1) + log(N+2) + ... + log(N+M)

由于它是最大元素，所以是否与log(N+M)相同？

还是因为它是M个元素的总和，所以是M*log(N+M)？

- yerzhan7

Answer 1

重要的规则是：

• Log a + Log b = Log ab
• Log a - Log b = Log a/b

---

将Log 2、Log 3，...Log N-1加减到给定值。

这将给出Log 2 + Log 3 + ... + Log (N+M) - (Log 2 + Log 3 + ... + Log (N-1))。

第一部分计算结果为Log ((N+M)!)，减法符号后面的部分计算结果为Log ((N-1)!)。

因此，复杂度为Log ( (N+M)! / (N-1)! )。

---

更新： OP在评论中提出了另一个好问题。

如果我们有N + N^2 + N^3，它会缩小到只有N^3（最大元素），对吗？为什么我们不能在这里应用相同的逻辑——log(N+M) - 最大元素？

如果我们只有两个看起来像Log(N) + Log(M+N)的项，那么我们可以将它们合并，并说它们肯定小于2 * Log(M+N)，因此它们为O(Log (M+N))。

然而，如果项目数量和最高价值之间存在关系，则存在这样的关系使得计算略微不太直接。

例如，添加2个(Log N)的大O为O(Log N)，而N个Log N的总和的大O不是O(Log N)，而是O(N * Log N)。

在给定的求和中，值和总数取决于M和N，因此我们不能将这种复杂度作为Log(M+N)，但我们肯定可以将其写作M * (Log (M+N))。

如何？给定求和中的每个值都小于或等于Log(M + N)，并且共有M个这样的值。因此，这些值的求和将小于M * (Log (M+N))，因此为O(M * (Log (M+N)))。

---

因此，两个答案都是正确的，但O(Log ( (N+M)! / (N-1)! ))是一个更紧密的界限。

- displayName

---

减法从哪里开始？它不在OP的问题中。 - Samer Tufail

但是如果我们有 N + N^2 + N^3，它将缩减为仅为 N^3（最大元素），对吗？ 为什么我们不能在这里应用相同的逻辑 - log(N+M) - 最大元素？ - yerzhan7

@SamerTufail：在我的回答的第四行中：“添加和减去Log 2 ...”。 - displayName

值得一提的是，对于大的N和M，斯特林逼近公式表明这将近似于(N+M) log (N+M) - (N-1) log(N-1) - M + 1。对此还有一些校正项，我没有进行严格评估。 - jwimberley

@jwimberley：你可以编辑答案并在答案中添加一个新的部分。这是一个很好知道的信息。 - displayName

Answer 2

如果M不依赖于N且不变，则复杂度为O(log(N))。

对于k，例如0 <= k <= M和N>=M和N>=2，

log(N+k)=log(N(1+k/N)) = log(N) + log(1+k/N) <= log(N) + log(2) 
<= log(N) + log(N) <= 2 log(N)

所以

log(N) + log(N+1) + log(N+2) + ... + log(N+M) <= (M+1)2 log(N)

所以，大O表示法中的复杂度是：log(N)

回答你的问题：

1）是的，因为所有元素都少于或等于log(N+M)个固定数目。

2）实际上有M + 1个元素（从0到M）。

我要指出的是，O((M+1)log(N+M))是O(log(N))。

- Jean-Claude Colette