algorithm - 使用快速排序和二进制搜索的集合差异的复杂性是什么？

Question

我们有两个集合 A，B，我们想计算集合差异 A - B，我们将使用快速排序对 B 的第一个元素进行排序，其平均复杂度为 O(n * log n)，并且在我们用二进制搜索 B 中的 A 中的每个元素之后搜索具有复杂度 O(log n) 的整个集合差异算法描述了哪种复杂度？如果我们考虑使用快速排序和二分搜索。我尝试使用以下算法计算集合差异的复杂性： O(n * log n) + O(log n) = O(n * log n + log n) = O(log n * (n + 1)) = O((n + 1) * log n)。这是对的吗 ？

Answer 1

首先，常数在 O 表示法中并不真正计数，因为多项式的增长速度快于常数，因此1将由 拥有n，这意味着 O((n + 1) * log n) 只是 O(n * log n)。

现在重要的问题 - 假设 A 有m元素，您需要进行m二进制搜索，每个元素的复杂度为 O(log n)。所以总的来说，复杂度应该是 O(n * log n) + O(m * log n) = O((n + m) * log n)。

Answer 2

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

http://en.wikipedia.org/wiki/Big_O_notation#Properties

如果一个函数可能以 n 中的多项式为界，那么随着 n 趋于无穷大，人们可能会忽略多项式的低阶项。