¿Cómo encontraría la complejidad de tiempo y espacio de este código?

Question

Tengo dificultades para encontrar espacio y complejidad del tiempo para este código que escribí para encontrar el número de palíndromos en una cadena.

/**
 This program finds palindromes in a string.
*/

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

int checkPalin(char *str, int len)
{
    int result = 0, loop;

    for ( loop = 0; loop < len/2; loop++)
    {

        if ( *(str+loop) == *(str+((len - 1) - loop)) )
            result = 1;
        else {
            result = 0;
            break;
        }
    }

    return result;
}

int main()
{
    char *string = "baaab4";
    char *a, *palin;

    int len = strlen(string), index = 0, fwd=0, count=0, LEN;
    LEN = len;

    while(fwd < (LEN-1))
    {
        a = string+fwd;
        palin = (char*)malloc((len+1)*sizeof(char));    

        while(index<len)
        {
            sprintf(palin+index, "%c",*a);
            index++;
            a++;

            if ( index > 1 ) {
                *(palin+index) = '\0';
                count+=checkPalin(palin, index);
            }
        }

        free(palin);
        index = 0;
        fwd++;
        len--;
    }

    printf("Palindromes: %d\n", count);
    return 0;
}

Le di una oportunidad y esto es lo que pienso:
En Main tenemos dos mientras los bucles. El exterior corre sobre toda la longitud-1 de la cadena. Ahora aquí está la confusión, el bucle interno mientras que se extiende sobre toda la longitud primero, luego N-1, luego N-2, etc. para cada iteración del exterior mientras. Entonces eso significa que nuestra complejidad del tiempo será O(n(n-1)) = O(n^2-n) = O(n^2)? Y para la complejidad del espacio inicialmente asigno espacio para la longitud de la cadena+1, luego (longitud+1) -1, (longitud+1) -2 etc. Entonces, ¿cómo podemos encontrar la complejidad del espacio a partir de esto? Para la función de checkpalin su O(n/2).
Me estoy preparando para entrevistas y me gustaría entender este concepto.
Gracias

Answer 1

No olvide que cada llamada a CheckPalin (que hace cada vez a través del bucle interno de Main) ejecuta un bucle index / 2 veces dentro de checkpalin. Su cálculo de la complejidad del tiempo del algoritmo es correcto, excepto esto. Ya que index se vuelve tan grande como n, esto agrega otro factor de n a la complejidad del tiempo, dando o (n³).

En cuanto a la compleja espacial, se asigna cada vez a través del bucle exterior, pero luego lo libere. Entonces la complejidad del espacio es o (n). (Tenga en cuenta que o (n) == O (n/2). Es solo el exponente y la forma de la función lo que es importante).

Answer 2

Para la complejidad del tiempo, su análisis es correcto. Es O (n^2) debido a la n+(n-1)+(n-2)+...+1 pasos. Para la complejidad del espacio, generalmente solo cuenta el espacio necesario en un momento dado. En su caso, la memoria más adicional que necesita es O (n) la primera vez a través del bucle, por lo que la complejidad del espacio es lineal.

Dicho esto, este no es un código especialmente bueno para verificar un palíndromo. Puede hacerlo en el tiempo o (n) en el espacio o (1) y tener un código más limpio y más claro para arrancar.

Gah: no leí lo suficiente. La respuesta correcta se da en otro lugar.