最小复杂度的Anagram算法

Question

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

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

但是,该算法的时间复杂度为O(n),我无法提出复杂度较低的算法.有人知道吗？

Answer 1

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