c - 具有最小复杂度的 Anagram 算法

Question

我最近被要求设计一种算法来检查两个字符串是否是彼此的变位词。我的目标是最小化空间和时间复杂度，所以我想出了这个算法:

1. 创建一个包含 26 个元素的数组，每个元素都初始化为零。
2. 遍历第一个字符串，并为每个字符递增与该字符对应的数组元素。
3. 遍历第二个字符串，对每个字符，递减该字符对应的数组元素。
4. 扫描阵列。如果所有元素都为0，则这两个字符串是变位词。

但是，这个算法的时间复杂度是O(n)，我想不出一个复杂度更低的算法。有人知道吗？

Answer 1

您的算法是渐近最优的。不可能在比 Ω(n) 更好的时间内解决这个问题。要看到这一点，假设存在可以在 o(n) 时间内解决问题的算法 A(请注意，这里是 little-o of n)。然后对于任何 1 > ε > 0，存在一些 n 使得对于任何大小至少为 n 的输入，算法必须在至多 εn 步中终止。设置 ε = 1/3 并考虑算法的任何输入，对于该 ε 的上述 n，长度至少为 n。由于该算法可以查看两个字符串中最多 1/3 的字符，因此该函数必须有两个不同的输入，一个是一对变位词，另一个不是，这样算法会查看每个输入字符的相同子集。然后该函数必须在每种情况下产生相同的输出，因此至少有一个输入是错误的。我们遇到了一个矛盾，所以这样的算法一定不存在。