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

Question

C++ 文档说is_permutation最坏情况的时间复杂度是 O(N^2)：

最多 O(N^2) 次谓词应用，或者如果序列已经相等，则恰好为 N，其中 N=std::distance(first1, last1)。但是，如果 ForwardIt1 和 ForwardIt2 满足 LegacyRandomAccessIterator 和 std::distance(first1, last1) != std::distance(first2, last2) 的要求，则不会应用谓词。

然而，在我看来，最坏的情况应该是 O(NlogN) - 我们能不能只对O(NlogN)中的两个序列进行排序，然后比较它们呢？我缺少什么？

Answer 1

is_permutation不要求范围可排序。它仅使用bool-valued 比较谓词。

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