algorithm - 对数函数求和的复杂度是多少

Question

我有一个在大 O 中具有以下复杂度的算法:

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

它是否与 log(N+M) 相同，因为它是最大的元素？

或者是 M*log(N+M) 因为它是 M 元素的总和？

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)! )。

---

UPDATE 在 OP 在评论中提出了另一个好问题之后:

If we have N + N^2 + N^3, it will reduce to just N^3 (the largest element), right? Why we can't apply the same logic here - log(N+M) - largest element?

如果我们只有两个看起来像 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 *登录 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)! )) 是一个更严格的界限。