Come verificare la complessità dello spazio di questo programma?

Question

Come verificare la complessità dello spazio di questo programma?

#1 da (2 voti)

1

Ho scritto la mia versione della funzione strstr in c. Sto usando una matrice temporanea di dimensione 26. Quindi la complessità spaziale O (1) o O (n)? Questo è il mio codice:

void strcheck(char t[], int n, char p[], int m)
{
    int i, j, k;
    int temp[26];

    for (i = 0; i < 25; ++i)
        temp[i] = 0;
    for (i = 0; i < n; ++i)
    {
        k = t[i] - 'a';
        temp[k]++;
    }
    for (j = 0; j < m; j++)
    {
        k = p[j] - 'a';
        if (temp[k] > 0)
            temp[k]--;
        else
            break;
    }
    if (j == m)
        printf("string occured\n");
    else
        printf("not occured\n");
}

Il programma funziona correttamente, voglio solo sapere della complessità dello spazio. Grazie

c

posta coder005 19.06.2014 - 19:42

fonte

1 risposta

Leggi altre domande sui tag c

Esiste una struttura dati standard conosciuta che è una tabella hash che risolve le collisioni utilizzando un albero binario? Modello OpenSSL Client per comunicazione half duplex tramite socket

score 2 · Answer 1

2

Questo sta usando O (1) (anche Big-Theta (1), dato che l'uso migliore e il caso peggiore sono la stessa cifra) complessità dello spazio in quanto la quantità di spazio necessaria per eseguire l'operazione non aumentare con n.

risposta data 19.06.2014 - 19:53

fonte