具有此所需输出的算法的运行时间顺序是什么？

Question

有N个集合Ai到每个具有字符串条目的集合。一个集合的平均大小是K。

对于每个Ai，我们希望返回一个列表(或者更好的数据结构？)在不包括Ai的N-1个集合中，这些集合与Ai有多少共同的元素？

请不要害羞地用漂亮的数学论点给出详细的回答...：)

另外，这是一个标准问题吗?我可以在其他地方阅读更多关于它的信息吗？

Answer 1

基本上，通过执行两个集合的交集来生成每个结果列表元素。结果列表元素中有N-1个交叉点，可以归结为N-1 * IntersectTime。对于结果中的N个列表元素，其总和为N(N-1) * IntersectTime。之后，你必须对N-1个集合进行N次排序，所以仅仅为了对它们进行排序，你就有O(N²log )。

IntersectTime依赖于set的实现，对于一个典型的哈希集，这是O(k)。

所以最后我们有O(N²k) + O(N²log )= O(N²(k+log N)) =(如果我们假设k> log ) O(N²k)。

编辑:当你真的要实现它时，最好知道当你与两个集合相交时，你可以将结果用于2个结果列表元素，也就是说，对于第一个元素，你必须将A_1与N-1相交，对于A_2与N-2 (对于第一个元素，已经完成了与A_1的相交)，对于具有N-3个其他集合的A_3，最后对于没有任何元素的A_N。但这不会修改大O时间，它只是运行时的一半。

Answer 2

这是我的尝试-

我相信你可以将这个过程归结为: O(N * (C + S))

其中N是集合的数量，C是将N-1个集合与集合Ai进行比较所需的时间量，S是对N-1个集合进行排序所需的时间量。

比较是K项对K项的N-1次，所以(N-1)K^2次比较

排序需要log( N - 1 )时间。为了简单起见，我们可以将N-1缩短为N

因此，整个过程应该在O(N(NK^2 +log(N)内运行。

你应该对此持保留态度，我已经很长一段时间没有做过任何关于算法的事情了。还可能有一种更有效的方法来比较集合。