大O符号计算，O(n) * O(log n) = O(n log n)。

Question

我需要设计一个算法，能够在给定的O符号下进行一些计算。我已经有一段时间没有用O符号进行计算了，对如何将不同的O符号相加有点困惑。

O(n) * O(log n) = O(n log n)

O(n) + O(n) = O(2n) = O(n)

O(n) * O(log n) + O(n log n) = O(n log n) + O(n log n) = O(n log n)

这些正确吗？我还忽略了哪些规则？

- Androme

---

我已经编辑了标题（原来是 O(n) + O(log n) = O(n log n)）现在是正确的。 - ninjagecko

我的评论有些离题，但有些人可能会觉得它很有趣。在计算机科学中，符号O(log n)引起的困惑比我见过的任何东西都要多。几乎每个人似乎都认为O(log n)与O(1)不同——但实际上并不是这样。通过L'Hospital法则的应用，你可以证明它们是相同的。即使n等于10亿，我们也应该犹豫放弃一个简洁的算法来改进O(log n)到O(1)。因为这样做所获得的收益微乎其微（如果你不相信我，可以运行一下数字），而如果被放弃的算法是O(sqrt(n))，那么所获得的收益确实是存在的。 - thb

Answer 1

乘法的规则非常简单：查看链接

O(f) * O(g) = O(f * g)

如果你想让它适用于任意函数，那么两个O术语的总和更难计算。
但是，如果f ∈ O(g)，那么f + g ∈ O(g)。

因此，你的计算是正确的，但你原来的标题不正确；

O(n) + O(log n) = O(n)

- phihag

---

谢谢你，我也是这么想的，但在尝试处理算法时有点困惑:D 谢谢你的快速回复。 - Androme

是的，帖子标题中的关系是错误的：O(n) + O(log n) = O(n log n)。但是他在帖子中提到的关系是正确的：O(n) * O(log n) = O(n log n)。 - sch

更新了答案。由于O(log(n))是O(n)的子集，所以O(n) + O(log n) = O(n)。 - phihag

@WolframH 是的，那个定义过于非正式了。通过对集合定义最大值进行修正，现在它在技术上是正确的，但我认为它更难以阅读。 - phihag

为什么不直接写成“对于f = O(g)：O(f) + O(g) = O(g)”呢？ - Reinstate Monica