最小复杂度的字谜算法

Question

我最近被要求设计一个算法来检查两个字符串是否是另一个的字谜。我的目标是尽量减少空间和时间的复杂性，所以我想出了这个算法：

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

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

Answer 1

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

Answer 2

为了确保字符串是字符串，您需要比较整个字符串 - 那么它怎么会比o（n）更快？

Answer 3

您可以在早期退出时改善平均表现。在扫描第二个字符串时，如果在递减之前count [char]为0，那么您没有anagram，可以停止扫描。

另外，如果字符串比26个字符短，那么在最后一步中，只检查第一个字符串中的字符为零。

这不会改变大O，但它可以将您的平均运行时间更改为低于建议解决方案的2N + 26的水平，具体取决于您的数据。

Answer 4

int anagram (char a[], char b[]) { 

    char chars[26]; 
    int ana = 0; 
    int i =0; 

    for (i=0; i<26;i++) 
     chars[i] = 0; 


    if (strlen(a) != strlen(b)) 
     return -1; 

    i = 0; 
    while ((a[i] != '\0') || (b[i] != '\0')) { 
     chars[a[i] - 'a']++; 
     chars[b[i] - 'a']--; 
     i++; 
    } 

    for (i=0; i<26;i++) 
     ana += chars[i]; 

    return ana; 

} 


void main() { 

    char *a = "chimmy\0"; 
    char *b = "yimmch\0"; 

    printf ("Anagram result is %d.\n", anagram(a,b)); 


}