Come troverei la complessità del tempo e dello spazio di questo codice?

Question

Ho difficoltà a trovare la complessità di spazio e tempo per questo codice che ho scritto per trovare il numero di palindromi in una stringa.

/**
 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;
}

Ho dato un colpo e questo quello che penso:
In main abbiamo due mentre i loop. Quello esterno corre sull'intera lunghezza-1 della stringa. Ora ecco la confusione, il ciclo interno mentre si corre su tutta la lunghezza, quindi N-1, quindi N-2 ecc. Per ogni iterazione dell'esterno durante il ciclo. Anche questo significa che la nostra complessità temporale sarà O(n(n-1)) = O(n^2-n) = O(n^2)? E per la complessità dello spazio inizialmente assegno spazio per la lunghezza della stringa+1, quindi (lunghezza+1) -1, (lunghezza+1) -2 ecc. Quindi come possiamo trovare la complessità dello spazio da questo? Per la funzione checkparin è O(n/2).
Mi sto preparando per le interviste e vorrei capire questo concetto.
Grazie

Answer 1

Non dimenticare che ogni chiamata a CheckPalin (che fai ogni volta attraverso il ciclo interno di Main) esegue un loop index / 2 Tempi all'interno di CheckPalin. Il calcolo della complessità temporale dell'algoritmo è corretto tranne questo. Da index diventa grande come n, questo aggiunge un altro fattore di n alla complessità del tempo, dando O (n³).

Per quanto riguarda lo spazio, la compilazione, si alloca ogni volta attraverso il ciclo esterno, ma poi lo libererà. Quindi la complessità dello spazio è O (n). (Si noti che O (n) == O (n/2). È solo l'esponente e la forma della funzione che è importante.)

Answer 2

Per la complessità del tempo, la tua analisi è corretta. È O (n^2) a causa di N+(N-1)+(N-2)+...+1 passi. Per la complessità dello spazio, in genere conta solo lo spazio necessario in qualsiasi momento. Nel tuo caso, la memoria più aggiuntiva di cui hai mai bisogno è O (n) la prima volta attraverso il ciclo, quindi la complessità dello spazio è lineare.

Detto questo, questo non è un codice particolarmente buono per controllare un palindromo. Potresti farlo nello spazio O (n) e O (1) e avere in realtà un codice più pulito e più chiaro da avviare.

Gah: Non ho letto abbastanza da vicino. La risposta corretta è data altrove.