Comment calculer la notation Big-O sur le code suivant

Question

J'ai lu le sujet:

Big O, how do you calculate/approximate it?

Et ne suis pas sûr de ce que la notation Big-O pour la fonction suivante serait:

static int build_nspaces_pattern(const char * const value, char *pattern, 
     size_t sz_pattern) { 
    static char val_buffer[1025]; 
    char   *ptr, *saveptr; 
    size_t   szptrn; 
    ptrdiff_t  offset; 

    val_buffer[0] = '\0'; 
    strncat(val_buffer, value, sizeof(val_buffer) - 1); 
    val_buffer[sizeof(val_buffer) - 1] = '\0'; 

    pattern[0] = '^'; pattern[1] = '('; pattern[2] = '\0'; 

    for (ptr=strtok_r(val_buffer, ",", &saveptr); 
     ptr!=NULL; 
     ptr=strtok_r(NULL, ",", &saveptr) 
     ) { 
     szptrn = sz_pattern - strlen(pattern) - 1; 

     if (sanitize(ptr) != 0) { 
     return -1; 
     } 
     strncat(pattern, ptr, szptrn); 
     szptrn -= strlen(ptr); 
     strncat(pattern, "|", szptrn); 
    }  

    offset = strlen(pattern); 
    pattern[offset-1] = ')'; pattern[offset] = '$'; pattern[offset+1] = '\0'; 

    return 0; 
} 

Sanitize est O (n), mais la boucle for s'exécutera k fois (k est le nombre de virgules dans la chaîne). Donc, k * O (n) est toujours O (n), serait-ce O (n^2), O (k.n) ou autre chose?

Merci.

Answer 1

Regarde O (n) à moi, d'un coup d'oeil.

• strtok_r() itère à travers la chaîne d'origine = O (n)

• sanitize() que vous dites est O (n), mais cela est sans doute par rapport à la longueur du jeton plutôt que la longueur de la chaîne d'origine, longueur de sorte jeton multiplier par le nombre de jetons = O (n)

• strncat() finit par copier tous les originaux s Tring sans chevauchement = O (n)

• vous ajoutez un nombre fixe de caractères à la chaîne de sortie (^, (, ), $ et un couple de Null) = O (1)

• vous

  ajouter une | à la chaîne par jeton = O (n)

Mais attendez!

• vous appelez strlen() sur le motif de sortie pour chaque itération de la boucle = O (n^2)

Donc, il y a votre réponse.

Answer 2

Une façon d'aborder Je l'aime est de remplacer le code avec le temps en cours d'exécution, donc par exemple

val_buffer[0] = '\0'; 
strncat(val_buffer, value, sizeof(val_buffer) - 1); 
val_buffer[sizeof(val_buffer) - 1] = '\0'; 

devient

O(1) 
O(n) (* Assume the size of value is the size of the input *) 
O(1) 

Une boucle

for each k in value { 
    strlen(value) 
} 

devient

O(n) { 
    O(n) 
} 

ou quelque chose comme une telle notation, que vous pouvez ensuite faire en O(n) * O(n) = O(n^2).Vous pouvez ensuite résumer tous les grands-oh fois énumérés pour obtenir votre temps de complexité finale. Une astuce similaire consiste à commencer par aligner tout votre code avec le nombre de travail effectué, puis à supprimer le code qui fait le vrai travail en ne laissant que les chiffres. Ensuite, en utilisant des mathématiques simples pour simplifier les comptes. À savoir,

count = 0; 
for (i = 0; i < k; i++) { 
    count++ 
} 

est facile de voir être remplacé par count = k.

Answer 3

Pourquoi tout le monde suppose-t-il que strlen = O (n)? Je pensais que O (n) était seulement pour les boucles.