有N个集合Ai到一个每个都有字符串项一个集合的平均大小是k。
对于每个人工智能，我们希望返回一个列表（或者更好的数据结构？）不包括Ai的N-1个集合中，按集合与Ai共有多少个元素排序？
请不要羞于给出一个详细的回答，并给出一个很好的数学论点……：）
这也是一个标准问题，我能在什么地方读到更多吗？
最佳答案
基本上，通过执行两个集合的交集来生成每个结果列表元素。结果列表元素中有n-1个交集，可以归结为n-1*intersecttime。对于结果中的n个列表元素，其总和为n（n-1）*intersecttime。之后，您必须订购n乘以n-1台，因此仅订购它们，您就拥有o（n？logn）。
intersecttime取决于集合的实现，对于一个典型的散列集来说，这对您来说是o（k）。
所以最后我们得到了o（n~k）+o（n~logn）=o（n~2（k+logn））=（如果我们假设k>logn）o（n~k）。
编辑：当你真的希望这样做时，最好知道当你交叉两个集合时，你可以使用结果列表中的两个元素的结果，也就是说，第一个你必须将a_1与n-1交叉，将a_2与n-2交叉（与a_1的交叉已经在第一个元素处完成了）。对于有N-3个其他集合的A_3，最后对于没有集合的A_N但这并没有修改big-o时间，它只是运行时的一半。
关于algorithm - 具有所需输出的算法的运行时间顺序是什么？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/5525050/