为什么 is_permutation O(n^2) 的最坏情况？
Why is worst case of is_permutation O(n^2)?
C++ 文档说 is_permutation 的最坏情况时间复杂度是 O(N^2):
At most O(N^2) applications of the predicate, or exactly N if the sequences are already equal, where N=std::distance(first1, last1). However if ForwardIt1 and ForwardIt2 meet the requirements of LegacyRandomAccessIterator and std::distance(first1, last1) != std::distance(first2, last2) no applications of the predicate are made.
然而，IMO 在最坏的情况下应该是 O(NlogN) - 我们可以不只对 O(NlogN) 中的两个序列进行排序然后比较它们吗？我错过了什么？
is_permutation 不要求范围可排序。它仅使用 bool 值比较谓词。
此外，范围是不可变的，因此即使可以对它们进行排序，排序也意味着在其中一个范围上创建索引。这会将 O(N) 内存成本添加到 O(NlogN) 索引生成成本中。
C++ 文档说 is_permutation 的最坏情况时间复杂度是 O(N^2):
At most O(N^2) applications of the predicate, or exactly N if the sequences are already equal, where N=std::distance(first1, last1). However if ForwardIt1 and ForwardIt2 meet the requirements of LegacyRandomAccessIterator and std::distance(first1, last1) != std::distance(first2, last2) no applications of the predicate are made.
然而，IMO 在最坏的情况下应该是 O(NlogN) - 我们可以不只对 O(NlogN) 中的两个序列进行排序然后比较它们吗？我错过了什么？
is_permutation 不要求范围可排序。它仅使用 bool 值比较谓词。
此外，范围是不可变的，因此即使可以对它们进行排序，排序也意味着在其中一个范围上创建索引。这会将 O(N) 内存成本添加到 O(NlogN) 索引生成成本中。