c++ 中算法的复杂度 std::includes
Complexity of algorithm std::includes in c++
算法 std::includes 取两个排序范围并检查 set2 是否在 set1 中（即 set2 的每个元素是否包含在 set1 中）？
我想知道为什么eel.is/c++draft说这个算法的复杂度最多是2·(N1+N2-1)次比较？
相同的声明在：
1. cppreference
2. cplusplus
在我看来，它最多应该只是 2·N1 比较，最坏的情况是 max(set2) >= max(set1).
对于交错集合，例如 1,3,5,7..., 2,4,6,8,...，必须比较每个集合的第一项是否相等，如果失败，一个人必须从排序队列中消耗较小的项目。另一种方法是先比较 a<b，然后比较 b<a，假设只有小于运算符可用。无论哪种方式，这都会导致 2(N1+N2+c) 复杂度。
这种复杂性分析可以随着三向比较的引入而改变 <=> 到 (N1+N2-1)。
编辑：是的，你是对的。该算法在每次迭代中推进第一个指针，并在第一个 pointer/iterator 到达末尾时停止。因此最多会有 N 次迭代。这与推进 iterator2 所需的步骤无关。失败在示例算法中，它不处理 set1={1,2,3}, set2={3,3,3,X} 的情况，有重复。
我同意你的结论。 中的 interleaved sets 示例是错误的，因为算法将在 2 < 3.
时提前退出
cppreference 上的示例实现有一个循环，在每次迭代时递增 first1，在 first1 == last1 时递增 returns，每次迭代最多执行 2 次比较，并且不包含嵌套循环。除了 2xN1 比较，我看不出这还能做什么。
我在 C++ 标准草案的 github 上创建了一个 issue。
ISO C++ 标准委员会的 Richard Smith 就此进行了一些讨论。
从一开始他就拒绝了混淆std::includes意图的问题。但最终同意在澄清规范后重新审视功能的复杂性：
The complexity requirements are consistent with the current
description, and should be fixed if/when the description is fixed to
actually describe what the algorithm is "supposed' to do. Seems like
LWG is already on the case. I'll reply to that lib thread to request
that the complexity be revisited when the spec is fixed.
算法 std::includes 取两个排序范围并检查 set2 是否在 set1 中（即 set2 的每个元素是否包含在 set1 中）？
我想知道为什么eel.is/c++draft说这个算法的复杂度最多是2·(N1+N2-1)次比较？
相同的声明在：
1. cppreference
2. cplusplus
在我看来，它最多应该只是 2·N1 比较，最坏的情况是 max(set2) >= max(set1).
对于交错集合，例如 1,3,5,7..., 2,4,6,8,...，必须比较每个集合的第一项是否相等，如果失败，一个人必须从排序队列中消耗较小的项目。另一种方法是先比较 a<b，然后比较 b<a，假设只有小于运算符可用。无论哪种方式，这都会导致 2(N1+N2+c) 复杂度。
这种复杂性分析可以随着三向比较的引入而改变 <=> 到 (N1+N2-1)。
编辑：是的，你是对的。该算法在每次迭代中推进第一个指针，并在第一个 pointer/iterator 到达末尾时停止。因此最多会有 N 次迭代。这与推进 iterator2 所需的步骤无关。失败在示例算法中，它不处理 set1={1,2,3}, set2={3,3,3,X} 的情况，有重复。
我同意你的结论。 2 < 3.
cppreference 上的示例实现有一个循环，在每次迭代时递增 first1，在 first1 == last1 时递增 returns，每次迭代最多执行 2 次比较，并且不包含嵌套循环。除了 2xN1 比较，我看不出这还能做什么。
我在 C++ 标准草案的 github 上创建了一个 issue。 ISO C++ 标准委员会的 Richard Smith 就此进行了一些讨论。
从一开始他就拒绝了混淆std::includes意图的问题。但最终同意在澄清规范后重新审视功能的复杂性：
The complexity requirements are consistent with the current description, and should be fixed if/when the description is fixed to actually describe what the algorithm is "supposed' to do. Seems like LWG is already on the case. I'll reply to that lib thread to request that the complexity be revisited when the spec is fixed.