O(N)排列检测

Question

这个答案 通过比较两个字符串的内容来确定它们是否为排列。如果它们包含相同数量的每个字符，那么它们显然是排列。这可以在O(N)时间内完成。

我不喜欢这个答案，因为它重新发明了is_permutation 的设计目的。话虽如此，is_permutation 的复杂度为：

最多应用谓词的次数为O(N²)，或者如果序列已经相等，则恰好为N，其中N=std::distance(first1, last1)

因此，在手动编写的算法比is_permutation慢几个数量级的情况下，我不能提倡使用is_permutation。但是，标准库的实现者肯定不会错过这样一个明显的改进吧？那么为什么is_permutation的复杂度是O(N²)呢？

- Jonathan Mee

---

看起来是时间/空间权衡 - 更快的解决方案需要一个由您排列的值索引的计数数组。如果这些值是字节，则为256个条目的数组，如其他答案中所示。如果它们更大，那么该数组可能会过大而无法接受。 - user2404501

@Aaron：std::is_permutation无法进行排序，因为它不知道如何按照元素之间的顺序排序（因为它不假设这样的排序有意义！）。 它只知道如何测试它们是否相等。 - moonshadow

很棒且引人入胜的评论，直到现在我才注意到is_permutation函数不需要定义小于号运算符。 - Jonathan Mee

“我无法提倡使用is_permutation，如果它比手写算法慢出指数倍的话。” 除非你的手写算法是O(0)，否则你可以放心，is_permutation一定不可能慢出指数倍。 - Paul Draper

@JonathanMee：一个显著特征是，标准库（STL）算法和数据结构需要小于运算符的所有重载或专门化都可以采用另一个比较函数。 - MSalters

Answer 1

is_permutation 函数适用于几乎所有数据类型。但是，您提供的链接中的算法仅适用于具有少量值的数据类型。

这与 std::sort 的时间复杂度为 O(N log N)，而计数排序的时间复杂度为 O(N) 相同的原因。

- MSalters

---

我不能买那个，而不是用 int[] 计数字符，我们可以使用 long long[] 来节省空间，并且仍然可以在 O(N) 的时间内运行。 - Jonathan Mee

@JonathanMee 你怎么知道要制作多少个桶？如果数组的元素在INT_MIN到INT_MAX范围内，则需要一个巨大的数组。 - NathanOliver

@doublep 负数数组是 long long[numeric_limits<char>::max - numeric_limits<char>::min]。与性能提升相比，这实际上是一个非常小的数组。 - Jonathan Mee

对于类型为char的字符串可以使用该函数。那么对于整型数组或者long long数组呢？ - NathanOliver

更糟糕的是，使用数组假设数据类型为整数。但如果您的集合是 std::vector<std::string> 呢？也就是说，您不是在寻找单词中字母的排列，而是句子中单词的排列？您需要一个 std::map<std::string, int> 来统计每个单词的出现次数，但是该映射本身并没有 O(1) 访问。 - MSalters

Answer 2

我写了那个答案。

当字符串的value_type为char时，查找表中所需的元素数为256。对于两个字节的编码，为65536。对于四个字节的编码，查找表将具有超过40亿个条目，可能需要16 GB的空间！而且大部分都没用到。

所以首先要认识到，即使我们将类型限制为char和wchar_t，它仍然可能是不可行的。同样，如果我们想在int类型的序列上执行is_permutation，也是如此。

我们可以为大小为1或2个字节的整数类型创建std::is_permutation<>的特化版本。但这有点像std::vector<bool>，并非每个人都认为它是一个好主意。

我们还可以使用基于std::map<T, size_t>的查找表，但这可能会导致大量分配内存，因此可能无法提高性能（或者至少不总是）。不过，值得实现一个进行详细比较。

总之，我不认为C++标准没有包含针对char的高性能版本的is_permutation是有问题的。首先，因为在现实世界中，我不确定它是否是模板最常见的用法；其次，STL并不是算法的全部和终极目标，特别是当领域知识可以用于加速计算特殊情况时。

如果is_permutation针对char在实际应用中非常常见，C++库实现者可以提供一个专门针对它的特化版本。

- John Zwinck

---

但这有些让人想起了 std::vector<bool>，而并不是每个人都认为这是一个好主意。我不同意。std::vector<bool> 不是一个好主意的原因是它影响了内存布局，使得 vector<bool> 不是一个真正的标准容器。而 is_permutation<char> 则没有这些问题，可以成为完全合适的优化。 - orlp

Answer 3

你引用的答案适用于char，它假定它们是8位（不一定如此），因此每个值只有256种可能性，并且您可以便宜地从每个值转换为数字索引以用于查找计数表（对于这种情况下的char，值和索引是相同的东西！）

它生成了每个字符串中每个char值出现的次数的计数；然后，如果这些分布对于两个字符串都相同，则这些字符串彼此相互排列。

时间复杂度是什么？

你必须遍历每个字符串的每个字符，因此对于长度为M和N的两个输入，需要M+N步

每个步骤都涉及在给定字符处增加固定大小表中的计数，因此是恒定的时间

因此，总体时间复杂度为O（N+M）：线性，正如你所描述的那样。

现在，std::is_permutation对其输入没有作出任何假设。它不知道仅有256种可能性，或者确实不知道它们是否被界限。它不知道如何将输入值转换为可以用作索引的数字，更不用说如何在常量时间内执行此操作。它唯一知道的是如何比较两个值是否相等，因为调用者提供了该信息。

所以，时间复杂度：

我们知道它必须在某个时候考虑每个输入的每个元素

对于它以前没有见过的每个元素（我将把如何确定这一点以及为什么不影响大O复杂性的讨论留给练习），我们知道它不能将元素转换为任何类型的索引或键来进行计数表，因此它无法计算出该元素存在多少个匹配项，这比线性遍历两个输入查看有多少个元素匹配更好。

因此，复杂度最好是二次方的。

- moonshadow

---

“最好也只能做到二次方复杂度”。当然，平均情况下可以做到O(Nlog(N))——先对范围进行排序，然后再比较？ - Aaron McDaid

@Aaron: 不是使用目前的签名；BinaryPredicate函数会在其输入相等时返回true，在不等时返回false，但是为了进行排序，你需要能够施加一种顺序，而不仅仅是测试相等性，因此你需要让BinaryPredicate函数能够返回(小于/大于/等于)而不是(等于/不等于)，这可能会限制您可以处理的值的类型。 - moonshadow

当然，如果你愿意承担更多的事情，你可以做得更好。你可以想象一种不那么通用的is_permutation形式，它接受一个元素并产生哈希键的函数，这可能会让你回到平均线性复杂度，如果你在哈希表中存储计数。但这不是完全通用的std::is_permutation所做的。 - moonshadow

实际上您还需要比较这两个表。当然，如果您可以假设char有256个可能的值，那么它是O(256) < O(N)的。此外，对于长度为M和N的两个字符串，如果 M!= N，则可以在O(1)的时间内判断它们是否是排列。只有在M==N时才需要计算字符数，而此时显然只需O(N)即可。 - MSalters

@MSalters：比较两个固定大小的表是常数时间。 - moonshadow