n 个向量的交集
intersection of n vectors
我是编程新手，我最近遇到了一个问题，即查找已排序整数的 n 个向量（int 向量）的交集。我想出的方法复杂度为 O(n^2)，我使用的是 std::set_intersect 函数。
我想出的方法是使用两个向量：第一个向量对应于我拥有的第一个向量，第二个向量对应于第二个向量。我在两个上调用 set intersection 并覆盖第一个向量，然后在第二个向量上使用 vector clear 函数。然后我将下一个向量覆盖为第二个向量，并重复该过程，最终返回第一个向量。
我相信有更有效的方法来解决这个问题，但目前，我想不出更有效的方法。对此问题的任何帮助将不胜感激。
幸运的是，我认为可以对
算法的复杂性。
std::set_intersection 在大小为 n1 和 n2 的输入集上的复杂度是
O(n1 + n2)。
您可以采用原始向量并在单次消除中将它们相交
锦标赛风格，也就是说，在第一轮中，您将第一轮和第二轮相交
向量，第 3 和第 4，第 5 和第 6，等等；在
第二轮你穿过第一个和第二个路口，第三个和第四个路口，
等等；重复直到最后一轮只产生一个交叉点。
每轮幸存的所有向量的大小之和不超过
回合开始时矢量大小总和的一半，
所以这个算法总共需要 O(N) 时间（也就是 O(N) space）
其中 N 是输入中所有原始向量的大小之和。
（它是 O(N)，因为 N + N/2 + N/4 + ... < 2N。）
所以，给定一个由已经排序的向量组成的输入，
算法的复杂度为O(N)。
您的算法以非常不同的顺序合并向量，
但是虽然我不是 100% 确定它也是 O(N)，但我强烈怀疑它是。
编辑：
关于如何在 C++ 中实际实现 "tournament" 算法，
这取决于你想努力优化它，
以及您输入的内容。
最简单的方法是创建一个新的向量列表；从旧列表中取出两个向量，将一个向量推入新列表，将两个旧向量合并到新向量中，销毁旧向量，希望图书馆有效地管理内存。
如果你想减少新向量的分配，然后重新使用向量
（正如您已经想到的那样）可能会有所帮助。如果输入数据结构是
例如，std::list<std::vector<int> >，您可以先将一个空向量推到该列表的前面。创建三个迭代器，一个指向新向量，一个指向列表中的前两个原始向量。
在最后两个迭代器处取向量的交集，
将结果写入第一个迭代器，然后清除第一个迭代器中的向量
最后两个迭代器。将最后两个迭代器各向前移动两个位置，
将第一个迭代器向前移动一个位置。重复。如果你到达一个状态
最后两个迭代器之一已经到达 end() 但另一个还没有，
擦除第一个迭代器和另一个迭代器之间的所有列表元素。
现在你又有了一个向量列表，只要有就可以重复
列表中有多个矢量。
如果输入是std::vector<std::vector<int> >那么压入一个元素
放在列表的前面是相对昂贵的，所以你可能想要一个
稍微复杂一点的算法。有很多选择，没有真的
我能想到的明显赢家。
这是另一个分析，表明您的算法已经是线性的。
假设您有一些向量集合，算法从集合中重复选择两个向量并用它们的交集替换它们，直到只剩下一个向量。您的方法符合此描述。我认为任何这样的算法都会在 set_intersection.
的所有执行中总共花费线性时间
假设 set_intersection 对大小为 x 和 y.
的向量最多进行 A * (x + y) 次操作
设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.
中花费的总时间
用不太正式的语言 - 要在 set_intersection 中花费 x + y 时间，您需要从集合中删除至少 (x + y)/2 个元素，因此花费超过线性时间执行 set_intersection 会让你 运行 out of elements.
我是编程新手，我最近遇到了一个问题，即查找已排序整数的 n 个向量（int 向量）的交集。我想出的方法复杂度为 O(n^2)，我使用的是 std::set_intersect 函数。
我想出的方法是使用两个向量：第一个向量对应于我拥有的第一个向量，第二个向量对应于第二个向量。我在两个上调用 set intersection 并覆盖第一个向量，然后在第二个向量上使用 vector clear 函数。然后我将下一个向量覆盖为第二个向量，并重复该过程，最终返回第一个向量。
我相信有更有效的方法来解决这个问题，但目前，我想不出更有效的方法。对此问题的任何帮助将不胜感激。
幸运的是，我认为可以对 算法的复杂性。
std::set_intersection 在大小为 n1 和 n2 的输入集上的复杂度是
O(n1 + n2)。
您可以采用原始向量并在单次消除中将它们相交
锦标赛风格，也就是说，在第一轮中，您将第一轮和第二轮相交
向量，第 3 和第 4，第 5 和第 6，等等；在
第二轮你穿过第一个和第二个路口，第三个和第四个路口，
等等；重复直到最后一轮只产生一个交叉点。
每轮幸存的所有向量的大小之和不超过
回合开始时矢量大小总和的一半，
所以这个算法总共需要 O(N) 时间（也就是 O(N) space）
其中 N 是输入中所有原始向量的大小之和。
（它是 O(N)，因为 N + N/2 + N/4 + ... < 2N。）
所以，给定一个由已经排序的向量组成的输入， 算法的复杂度为O(N)。
您的算法以非常不同的顺序合并向量， 但是虽然我不是 100% 确定它也是 O(N)，但我强烈怀疑它是。
编辑： 关于如何在 C++ 中实际实现 "tournament" 算法， 这取决于你想努力优化它， 以及您输入的内容。
最简单的方法是创建一个新的向量列表；从旧列表中取出两个向量，将一个向量推入新列表，将两个旧向量合并到新向量中，销毁旧向量，希望图书馆有效地管理内存。
如果你想减少新向量的分配，然后重新使用向量
（正如您已经想到的那样）可能会有所帮助。如果输入数据结构是
例如，std::list<std::vector<int> >，您可以先将一个空向量推到该列表的前面。创建三个迭代器，一个指向新向量，一个指向列表中的前两个原始向量。
在最后两个迭代器处取向量的交集，
将结果写入第一个迭代器，然后清除第一个迭代器中的向量
最后两个迭代器。将最后两个迭代器各向前移动两个位置，
将第一个迭代器向前移动一个位置。重复。如果你到达一个状态
最后两个迭代器之一已经到达 end() 但另一个还没有，
擦除第一个迭代器和另一个迭代器之间的所有列表元素。
现在你又有了一个向量列表，只要有就可以重复
列表中有多个矢量。
如果输入是std::vector<std::vector<int> >那么压入一个元素
放在列表的前面是相对昂贵的，所以你可能想要一个
稍微复杂一点的算法。有很多选择，没有真的
我能想到的明显赢家。
这是另一个分析，表明您的算法已经是线性的。
假设您有一些向量集合，算法从集合中重复选择两个向量并用它们的交集替换它们，直到只剩下一个向量。您的方法符合此描述。我认为任何这样的算法都会在 set_intersection.
假设 set_intersection 对大小为 x 和 y.
A * (x + y) 次操作
设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.
用不太正式的语言 - 要在 set_intersection 中花费 x + y 时间，您需要从集合中删除至少 (x + y)/2 个元素，因此花费超过线性时间执行 set_intersection 会让你 运行 out of elements.