我是编程新手，最近遇到了一个问题，即查找已排序整数的 n 个向量（整数向量）的交集。我想出的方法具有 O(n^2) 的复杂性，我正在使用 std::set_intersect 函数。
我想出的方法是使用两个向量：第一个向量对应于我拥有的第一个向量，第二个对应于第二个向量。我在两者上调用 set 交集并覆盖第一个向量，然后在第二个向量上使用向量清除功能。然后我将下一个向量覆盖到第二个向量，并重复该过程，最终返回第一个向量。
我确实相信有一种更有效的方式来解决这个问题，但目前，我想不出更有效的方式。对此问题的任何帮助将不胜感激。
幸运的是，我认为可以对算法的复杂性进行更严格的限制。
std::set_intersection大小为 n1 和 n2 的输入集的复杂度为 O(n1 + n2)。你可以把你的原始向量和它们相交以单淘汰锦标赛的方式，也就是说，在第一轮你相交第一个和第二个向量，第三个和第四个，第五个和第六个，依此类推；在第二轮中，您与第 1 和第 2 交叉点、第 3 和第 4 个交叉点相交，依此类推；重复直到最后一轮只产生一个交叉点。每轮幸存的所有向量的大小之和不超过一轮开始时向量大小之和的一半，因此该算法总共需要 O(N) 时间（也是 O(N) 空间）其中 N 是输入中所有原始向量的大小之和。（这是 O(N)，因为 N + N/2 + N/4 + ... < 2N。）
因此，给定一个由已经排序的向量组成的输入，算法的复杂度为 O(N)。
您的算法以非常不同的顺序合并向量，但虽然我不是 100% 确定它也是 O(N)，但我强烈怀疑它是。
编辑： 关于如何在 C++ 中实际实现“锦标赛”算法，这取决于您想要优化它的努力程度，以及您输入的性质。
最简单的方法是制作一个新的向量列表；从旧列表中取出两个向量，将一个向量推入新列表，将两个旧向量合并到新向量上，销毁旧向量，希望库有效地管理内存。
如果您想减少新向量的分配，那么重用向量（正如您已经想到的那样）可能会有所帮助。如果输入数据结构是std::list<std::vector<int> >，例如，您可以首先将一个空向量推到此列表的前面。制作三个迭代器，一个用于新向量，一个用于列表中原始前两个向量中的每一个。取最后两个迭代器的向量的交集，将结果写入第一个迭代器，然后清除最后两个迭代器的向量。将最后两个迭代器各向前移动两位，将第一个迭代器向前移动一位。重复。如果您达到最后两个迭代器之一已到达 end() 但另一个未到达的状态，请擦除第一个迭代器和另一个迭代器之间的所有列表元素。现在你又得到了一个向量列表，只要列表中有多个向量，就可以重复。
如果输入std::vector<std::vector<int> >将一个元素推到列表的前面，则相对昂贵，因此您可能需要稍微复杂一点的算法。有很多选择，我想不出真正明显的赢家。
这是另一个分析，表明您的算法已经是线性的。
假设您有一些向量集合，并且该算法重复地从集合中选择一些两个向量并用它们的交集替换它们，直到剩下一个向量。你的方法符合这个描述。我认为任何这样的算法在所有set_intersection.
假设set_intersection最多对大小为和A * (x + y)的向量进行操作。xy
设为K集合中所有向量的长度之和。它以输入 ( n) 的大小开始，并且不能低于零，因此最多可以更改n.
每次组合大小 ( x, y) 的向量时， 的值K至少减少(x + y)/2，因为结果必须比任一输入短。如果我们将所有调用相加，我们就得到了sum { (x + y)/2 } <= n，因为K变化不能超过n.
由此我们可以得出sum { A * (x + y) } <= 2 * A * n = O(n)。这里的左侧是在 中花费的总时间set_intersection。
用不太正式的语言 - 花x + y时间在set_intersection你需要从你的集合中删除至少(x + y)/2元素，所以花费超过线性时间执行set_intersection会使你用完元素。