This answer determines if two strings are permutations by comparing their contents. If they contain the same number of each character, they are obviously permutations. This is accomplished in O(N) time.
I don't like the answer though because it reinvents what is_permutation
is designed to do. That said, is_permutation
has a complexity of:
At most O(N2) applications of the predicate, or exactly N if the sequences are already equal, where
N=std::distance(first1, last1)
So I cannot advocate the use of is_permutation
where it is orders of magnitude slower than a hand-spun algorithm. But surely the implementer of the standard would not miss such an obvious improvement? So why is is_permutation
O(N2)?
is_permutation
works on almost any data type. The algorithm in your link works for data types with a small number of values only.
It's the same reason why std::sort
is O(N log N) but counting sort is O(N).
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With