c++ - 为什么 is_permutation 的最坏情况是 O(n^2)？

Question

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) 中的两个序列进行排序吗？然后只是比较它们？我错过了什么？

Answer 1

is_permutation 不要求范围是可排序的。它仅使用 bool 值比较谓词。

此外，范围是不可变的，因此即使可以对它们进行排序，排序也意味着在其中一个范围上创建索引。这会将 O(N) 的内存成本添加到 O(NlogN) 的索引生成成本中。