O(m * n) + O((m + n) * log(m + n)) 的复杂度评估是多少
What is the complexity evaluation of O(m * n) + O((m + n) * log(m + n))
我有以下 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)) 吗？
您可以将总输入大小视为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)。
我不认为你可以简化表达式。
确实，如果将 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)).
我有以下 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)) 吗？
您可以将总输入大小视为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)。
我不认为你可以简化表达式。
确实，如果将 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)).