Algoritmo de anagrama con complejidad mínima

Question

Recientemente me pidieron que diseñara un algoritmo que compruebe si dos cadenas son anagramas entre sí. Mi objetivo era minimizar la complejidad del espacio y el tiempo, así que se me ocurrió este algoritmo:

1. Crea una matriz de 26 elementos, cada uno inicializado a cero.
2. Recorre la primera cadena y para cada carácter, incrementa el elemento de la matriz correspondiente a ese carácter.
3. Recorre la segunda cadena y para cada carácter, disminuye el elemento de matriz correspondiente a ese carácter.
4. Escanee sobre la matriz. Si todos los elementos son 0, las dos cadenas son anagramas.

Sin embargo, la complejidad temporal de este algoritmo es O (n) y no puedo encontrar un algoritmo de menor complejidad. ¿Alguien sabe de uno?

Answer 1

Su algoritmo es asintóticamente óptimo. No es posible resolver este problema en un tiempo mejor que Ω (n). Para ver esto, suponga que existe un algoritmo A que puede resolver el problema en o (n) tiempo (tenga en cuenta que esto es poco-o de n aquí). Entonces para cualquier 1> épsilon; > 0, hay algunos n tales que para cualquier entrada de tamaño al menos n, el algoritmo debe terminar en un máximo & epsilon; n pasos. Set & epsilon; = 1/3 y considere cualquier entrada al algoritmo que sea de longitud al menos n para el n antes mencionado para este y épsilon ;. Dado que el algoritmo puede ver más de 1/3 de los caracteres en las dos cadenas, debe haber dos entradas diferentes a la función, una que es un par de anagramas y otra que no, de modo que el algoritmo observa el mismo subconjunto de los caracteres de cada entrada. La función tendría que producir la misma salida en cada caso, y por lo tanto sería incorrecta en al menos una de las entradas. Hemos llegado a una contradicción, por lo que no debe existir ese algoritmo.

Answer 2

Para estar seguro de que las cadenas son anagramas, necesita comparar las cadenas enteras, entonces, ¿cómo podría ser más rápido que o (n)?

Answer 3

Posiblemente podría mejorar el rendimiento promedio con salidas anticipadas. Mientras escanea la segunda cuerda, si count [char] es 0 antes de decrementar, no tiene un anagrama y puede detener el escaneo.

Además, si las cadenas son más cortas que 26 caracteres, en el último paso, marque solo los caracteres en la primera cadena para ceros.

Esto no cambia la gran O, pero puede cambiar su tiempo de ejecución promedio a algo menos que el 2N + 26 o de la solución propuesta, dependiendo de sus datos.

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)); 


}