O(N) 排列识别
O(N) Identification of Permutations
通过比较两个字符串的内容来判断两个字符串是否是排列。如果它们包含相同数量的每个字符，则它们显然是排列。这是在 O(N) 时间内完成的。
虽然我不喜欢这个答案，因为它重新发明了 is_permutation 的设计目的。也就是说，is_permutation 的复杂度为：
At most O(N2) applications of the predicate, or exactly N if the sequences are already equal, where N=std::distance(first1, last1)
所以我不能提倡使用 is_permutation，它比手工算法慢几个数量级。但标准的实施者肯定不会错过如此明显的改进吧？那么为什么 is_permutation O(N2)?
is_permutation 几乎适用于任何数据类型。 link 中的算法仅适用于具有少量值的数据类型。
这也是为什么std::sort是O(N log N)而计数排序是O(N)的原因。
那个答案是我写的
当字符串的value_type为char时，查找所需的元素个数table为256。对于双字节编码，65536。对于四字节编码编码，查找 table 将有超过 40 亿个条目，大小可能为 16 GB！而且大部分都不会被使用。
所以首先要认识到，即使我们限制类型为char和wchar_t，也可能仍然站不住脚。同样，如果我们想对 int.
类型的序列执行 is_permutation
我们可以对大小为 1 或 2 字节的整数类型进行 std::is_permutation<> 的特化。但这有点让人想起 std::vector<bool>，回想起来并不是每个人都认为这是个好主意。
我们也可以使用基于 std::map<T, size_t> 的查找 table，但这可能会占用大量资源，因此它可能不会带来性能上的优势（或者至少，并非总是如此）。不过，为了进行详细比较，可能值得实施一个。
总而言之，我不会因为 C++ 标准不包括 char 的 is_permutation 的高性能版本而受到指责。首先因为在现实世界中我不确定它是否是模板最常见的用途，其次因为 STL 并不是算法的全部和最终目的，特别是在领域知识可以用于加速特殊计算的情况下案例。
如果事实证明 is_permutation for char 在野外很常见，C++ 库实现者将有权为其提供专门化。
您引用的答案适用于 chars。它假设它们是 8 位（不一定是这种情况），因此每个值只有 256 种可能性，并且您可以廉价地从每个值转到数字索引以用于查找 table 计数（对于char在这种情况下，值和索引是一回事！）
它生成每个 char 值在每个字符串中出现的次数的计数；那么，如果两个字符串的这些分布相同，则这些字符串是彼此的排列。
时间复杂度是多少？
- 您必须遍历每个字符串的每个字符，因此对于长度为 M 和 N 的两个输入，需要执行 M+N 步
- 这些步骤中的每一步都涉及在 char 给定的索引处以固定大小 table 递增计数，常数时间也是如此
所以总体时间复杂度为 O(N+M)：线性，如您所述。
现在，std::is_permutation 不对其输入做出此类假设。它不知道只有 256 种可能性，或者它们实际上是有界的。它不知道如何从一个输入值到一个它可以用作索引的数字，更不用说如何在恒定时间内做到这一点。它唯一知道的是如何比较两个值是否相等，因为调用者提供了该信息。
所以，时间复杂度：
- 我们知道它必须在某个时候考虑每个输入的每个元素
- 我们知道，对于它以前从未见过的每个元素（我将讨论如何确定以及为什么这不会影响大 O 的复杂性作为练习），它无法将将元素放入任何类型的索引或键中以获得 table 的计数，因此它无法计算该元素存在的次数，这比线性遍历两个输入以查看有多少元素匹配更好
所以复杂度最多是二次的。
虽然我不喜欢这个答案，因为它重新发明了 is_permutation 的设计目的。也就是说，is_permutation 的复杂度为：
At most O(N2) applications of the predicate, or exactly N if the sequences are already equal, where
N=std::distance(first1, last1)
所以我不能提倡使用 is_permutation，它比手工算法慢几个数量级。但标准的实施者肯定不会错过如此明显的改进吧？那么为什么 is_permutation O(N2)?
is_permutation 几乎适用于任何数据类型。 link 中的算法仅适用于具有少量值的数据类型。
这也是为什么std::sort是O(N log N)而计数排序是O(N)的原因。
那个答案是我写的
当字符串的value_type为char时，查找所需的元素个数table为256。对于双字节编码，65536。对于四字节编码编码，查找 table 将有超过 40 亿个条目，大小可能为 16 GB！而且大部分都不会被使用。
所以首先要认识到，即使我们限制类型为char和wchar_t，也可能仍然站不住脚。同样，如果我们想对 int.
is_permutation
我们可以对大小为 1 或 2 字节的整数类型进行 std::is_permutation<> 的特化。但这有点让人想起 std::vector<bool>，回想起来并不是每个人都认为这是个好主意。
我们也可以使用基于 std::map<T, size_t> 的查找 table，但这可能会占用大量资源，因此它可能不会带来性能上的优势（或者至少，并非总是如此）。不过，为了进行详细比较，可能值得实施一个。
总而言之，我不会因为 C++ 标准不包括 char 的 is_permutation 的高性能版本而受到指责。首先因为在现实世界中我不确定它是否是模板最常见的用途，其次因为 STL 并不是算法的全部和最终目的，特别是在领域知识可以用于加速特殊计算的情况下案例。
如果事实证明 is_permutation for char 在野外很常见，C++ 库实现者将有权为其提供专门化。
您引用的答案适用于 chars。它假设它们是 8 位（不一定是这种情况），因此每个值只有 256 种可能性，并且您可以廉价地从每个值转到数字索引以用于查找 table 计数（对于char在这种情况下，值和索引是一回事！）
它生成每个 char 值在每个字符串中出现的次数的计数；那么，如果两个字符串的这些分布相同，则这些字符串是彼此的排列。
时间复杂度是多少？
- 您必须遍历每个字符串的每个字符，因此对于长度为 M 和 N 的两个输入，需要执行 M+N 步
- 这些步骤中的每一步都涉及在 char 给定的索引处以固定大小 table 递增计数，常数时间也是如此
所以总体时间复杂度为 O(N+M)：线性，如您所述。
现在，std::is_permutation 不对其输入做出此类假设。它不知道只有 256 种可能性，或者它们实际上是有界的。它不知道如何从一个输入值到一个它可以用作索引的数字，更不用说如何在恒定时间内做到这一点。它唯一知道的是如何比较两个值是否相等，因为调用者提供了该信息。
所以，时间复杂度：
- 我们知道它必须在某个时候考虑每个输入的每个元素
- 我们知道，对于它以前从未见过的每个元素（我将讨论如何确定以及为什么这不会影响大 O 的复杂性作为练习），它无法将将元素放入任何类型的索引或键中以获得 table 的计数，因此它无法计算该元素存在的次数，这比线性遍历两个输入以查看有多少元素匹配更好
所以复杂度最多是二次的。