temps et l'espace complexité (pour l'algorithme spécifique)

Question

Malgré les 30 dernières minutes, je passé à essayer de comprendre le temps et la complexité de l'espace mieux, je ne peux toujours pas déterminer avec certitude ceux de l'algorithme ci-dessous:

bool checkSubstr(std::string sub) 
{ 
    //6 OR(||) connected if statement(checks whether the parameter 
    //is among the items in the list) 
} 

void checkWords(int start,int end) 
{ 
    int wordList[2] ={0}; 
    int j = 0; 

    if (start < 0) 
    { 
     start = 0; 
    } 
    if (end>cAmount) 
    { 
     end = cAmount -1; 
    } 
    if (end-start < 2) 
    { 
     return; 
    } 
    for (int i = start; i <= end-2; i++) 
    { 
     if (crystals[i] == 'I' || crystals[i] == 'A') 
     { 
      continue; 
     } 
     if (checkSubstr(crystals.substr(i,3))) 
     { 
      wordList[j] = i; 
      j++; 
     } 
    } 
    if (j==1) 
    { 
     crystals.erase(wordList[0],3); 
     cAmount -= 3; 
     checkWords(wordList[0]-2,wordList[0]+1); 
    } 
    else if (j==2) 
    { 
     crystals.erase(wordList[0],(wordList[1]-wordList[0]+3)); 
     cAmount -= wordList[1]-wordList[0]+3; 
     checkWords(wordList[0]-2,wordList[0]+1); 
    } 

} 

Le La fonction vérifie fondamentalement une sous-chaîne de la chaîne entière pour des combinaisons de lettres prédéterminées (3 lettres, par exemple "SAN"). Longueur de la sous-chaîne peut être 4-6 pas de véritable moyen de déterminer, dépend de l'entrée (assez sûr que ce n'est pas pertinent, bien que pas 100%).

Mon raisonnement:

Si des lettres n dans la chaîne, le pire des scénarios, nous devons vérifier chacun d'entre eux. Encore une fois en fonction de l'entrée, cela peut être fait de trois façons.

1. Toutes les 6 chaînes de sous-longueur: Si tel est le cas, la fonction exécute n/6 fois, chaque 8 (ou 10?) Processus en cours d'exécution, ce qui (je pense) signifie que sa complexité est en O (n).
2. Toutes les sous-chaînes de longueur 4: à peu près la même raison ci-dessus, O (n).
3. 4 et 6 chaînes de sous-longueur mixte: ne peut pas voir pourquoi ce serait différent que le précédent 2. O (n)

En ce qui concerne la complexité de l'espace, je suis complètement perdu. Cependant, j'ai une idée: Si la fonction se reproduit pour la durée maximale, il faudra: n/4 x La quantité utilisée en une seule fois qui m'a fait penser qu'il devrait être O (n). Bien que, je ne suis pas convaincu que c'est correct. Je pensais que voir le processus de pensée de quelqu'un d'autre sur cet exemple m'aiderait à mieux comprendre comment calculer la complexité temporelle et spatiale. Merci pour votre temps.

EDIT: Permettez-moi de fournir des informations plus claires. Nous lisons une combinaison de 6 lettres différentes dans une chaîne, cela peut être (presque) n'importe quelle combinaison dans n'importe quelle longueur. 'cristaux' est la chaîne, et nous recherchons 6 combinaisons différentes de 3 lettres dans cette liste de lettres. Un peu comme un jeu de correspondance de bijoux. Maintenant, la liste de départ ne contient aucune correspondance (aucune des 6 combinaisons prédéterminées n'existe en premier lieu). Par conséquent, la seule façon dont les correspondances peuvent se produire à partir de ce moment est que les swaps ou les matches disparaissent. Une fois qu'un swap est traité par un code de niveau supérieur, la fonction est appelée pour rechercher des correspondances, et si une correspondance est trouvée, la fonction se répète après la suppression de la partie "match" de la chaîne.

Voyons maintenant comment le code recherche une correspondance. Pour démontrer un échange de 2 lettres:

ABA B-R ZIB (pas d'espace ou '-' dans la chaîne réelle, utilisée pour une meilleure démonstration),

B et R est permuté. Ce swap affecte uniquement les 6 lettres à partir de la 2ème lettre et se terminant à la 7ème lettre. En d'autres termes, les lettres que le premier A et le dernier B peuvent former sont identiques, avant et après le swap, donc pas de vérification des correspondances incluant ces mots. Donc une sous-chaîne de 6 lettres envoyée à l'algorithme de vérification. De même, si une correspondance formée disparaît (est supprimée de la chaîne), la portée des lettres affectées est de 4. Donc, quand je pensais au pire des cas, j'imaginais soit un swap créant une réaction en chaîne complète jusqu'à ce qu'il y ait pas assez de lettres pour former un match, ou chaque match se passe avec un échange. Encore une fois, je ne dis pas que c'est ainsi que nous devrions penser lorsque nous calculons la complexité du temps et de l'espace, mais c'est ainsi que fonctionne le code. J'espère que c'est assez clair si je ne le fais pas savoir et je peux fournir plus de détails. Il est également important de noter que la quantité de swap et les places font partie de l'entrée que nous lisons.

EDIT: Voici comment la fonction est appelée au niveau supérieur pour la première fois: checkWords(swaps[i]-2,swaps[i]+3);

Answer 1

longueur sous-chaîne peut être 4-6 aucun moyen de déterminer, dépend de l'entrée (assez sûr que ce n'est pas pertinent, bien que pas 100%).

Ce n'est pas ce que le code montre; la ligne if (checkSubstr(crystals.substr(i,3))) indique que les sous-chaînes ont toujours exactement 3 caractères. Si la longueur de la sous-chaîne varie, cela est pertinent car votre correspondance de sous-chaîne naïve se dégradera à O(N*M) dans le cas général, où N est start-end+1 (la taille de la chaîne d'entrée) et M est la taille de la sous-chaîne recherchée. Cela se produit car, dans le pire des cas, vous allez comparer M caractères pour chacun des caractères N de la chaîne source.

Le reste de cette réponse suppose que les sous-chaînes sont de taille 3, puisque c'est ce que montre le code.

Si les sous-chaînes ont toujours 3 caractères, c'est différent: vous pouvez supposer que checkSubstr() est O(1) parce que vous comparez toujours au plus 3 caractères. La majeure partie du travail se passe à l'intérieur de la boucle for, qui est O(N), où N est end-1-start.

Après la boucle, dans le pire des cas (lorsque l'un des if s est entré), vous effacez un groupe de caractères de crystal. En supposant qu'il s'agit d'une chaîne sauvegardée par un tableau en mémoire, il s'agit d'une opération O(cAmount) car tous les éléments après wordList[0] doivent être décalés. L'appel récursif passe toujours dans une plage de taille 4; il ne grossit pas et ne rétrécit pas avec la taille de l'entrée, donc vous pouvez également dire qu'il y a O(1) appels récursifs.

Ainsi, la complexité temporelle est O(N+cAmount) (où N est end-1-start), et de la complexité de l'espace est O(1).