O(m * n) + O((m + n) * log(m + n)) 的时间复杂度评估是什么？

Question

我有以下 Python 代码，a 和 b 是列表（我知道这不是获取交集的最佳方式）：

def get_intersection(a, b):
    a = set(a)
    b = set(b)
    c = sorted(list(a&b))
    return c

我们称len(a) - m和len(b) - n，因为没有关于a和b的附加信息。那么给定代码的时间复杂度是O(m) + O(n) + O(m * n) + O((m + n) * log(m + n))。

我肯定可以缩短O(m)和O(n)，因为它们远小于O(m * n)，但是对于O((m + n) * log(m + n))该怎么办呢？

我如何比较O(m * n)和O((m + n) * log(m + n))? 我应该在最终评估中保留O((m + n) * log(m + n))吗？

- vszholobov

---

渐近复杂度O(mn)肯定是占主导地位的。欢迎有新鲜微积分知识的人来证明它 :) - Eugene Sh.

m和n不是独立的组件。您合并的输入大小只是两个参数的累积大小。 - chepner

c = sorted(a&b)也可以; sorted返回一个列表，但可以对任何可迭代对象进行排序。 - chepner

这是一个非常奇怪的最坏情况。Raymond Hettinger在答案和该答案的评论中讨论了这个问题。简而言之，只有当您的数据本身使用了一个可笑的糟糕哈希函数时，才会发生这种情况。 - chepner

例如，没有最坏情况的整数集合可以实现O(n^2)的行为。这完全取决于集合中值的类型，而不是集合本身。 - chepner

Answer 1

您可以将总输入大小视为n;哪个参数对总输入大小做出了贡献并不重要。(两个极端情况是其中一个参数为空;将项目从一个参数移动到另一个参数不会改变您将要执行的工作总量。)

因此，set(a)和set(b)都是O(n)操作。 a & b也是O(n);您不需要比较a的每个元素和b的每个元素来计算交集，因为集合是基于哈希的。您基本上只需要进行O(n)常量时间查找。(我忽略了可怕的角落情况，这使得集合查找线性。如果您的数据具有不将每个项映射到相同值的哈希函数，则不会遇到最坏情况。) sorted(a&b)(无需先创建列表，但这也只是一个O(n)操作)需要O(n lg n)。

由于每个前面的操作按顺序执行，get_intersection的总复杂度为O(n lg n)。

- chepner

---

“你不能把总输入大小视为n”：不，这是错误的。m和n是独立的数字，m+n和mn也是如此。 - user1196549

但是没有必要将这两个列表分开创建。无论在整体复杂度中，m还是n都不会单独出现，只会以组合的形式 m + n 出现，因此其中一个数比另一个数大并不重要。举个例子，在图算法中，其时间复杂度为 O(n lg n + m)，其规模的变化取决于稀疏程度（m=O(n)）或密集程度（m=O(n^2)）。 - chepner

我已经不需要考虑产品“mn”了。 - chepner

我已经放弃考虑产品mn的任何需求：这是错误的。 - user1196549

这是错误的。渐近复杂度就是渐近复杂度。你不能挑选自己喜欢的术语，更不能忽视给你的表达方式。 - user1196549

Answer 2

我认为你无法简化这个表达式。

事实上，如果你将m设置为一个固定值，比如5，你就有了一个复杂度。

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

第一项被吸收。

但是如果你设置m = n，

n² + 2n log(2n) = O(n²)

这次第二项被吸收了。因此你能写的只有

O(mn + (m+n) log(m+n)).

通过变量的改变，使得s为和，p为积。

O(p + s log(s)).

- user1196549

---

你的答案对于时间复杂度为O(m * n) + O((m + n) * log(m + n))的算法是正确的，但我错误地假设Python中求交集的时间复杂度是O(m * n)。事实上，正如chepner在评论中指出的那样，它的时间复杂度是O(m + n)。因此，对于我的代码，最终的时间复杂度为O(m + n) + O((m + n) * log(m + n)) = O((m + n) * log(m + n))。 - vszholobov