这个答案 通过比较两个字符串的内容来确定它们是否为排列。如果它们包含相同数量的每个字符,那么它们显然是排列。这可以在O(N)时间内完成。
我不喜欢这个答案,因为它重新发明了is_permutation
的设计目的。话虽如此,is_permutation
的复杂度为:
最多应用谓词的次数为O(N2),或者如果序列已经相等,则恰好为N,其中
N=std::distance(first1, last1)
因此,在手动编写的算法比is_permutation
慢几个数量级的情况下,我不能提倡使用is_permutation
。但是,标准库的实现者肯定不会错过这样一个明显的改进吧?那么为什么is_permutation
的复杂度是O(N2)呢?
is_permutation
函数不需要定义小于号运算符。 - Jonathan Meeis_permutation
一定不可能慢出指数倍。 - Paul Draper