complexité algorithme

Question

Je suis en train de calculer la complexité de l'algorithme suivant

private static List<int> GetIndexes(string strippedText, string searchText) 
    { 
     List<int> count = new List<int>(); 
     int index = 0; 
     while (strippedText.Length >= index && index != -1) 
     { 
      index = strippedText.IndexOf(searchText.Trim(), index, 
             StringComparison.OrdinalIgnoreCase); 
      if (index != -1) 
      { 
       count.Add(index); 
       index++; 
      } 
      else continue; 
     } 
     return count; 
    } 

Je sais que la boucle a une complexité de O(n) si des augmentations de comptage de 1 à chaque itération, mais les incréments dépend des indices trouvés . à chaque itération, il peut incrémenter 1 ou strippedText.lenght().

Une idée?

Answer 1

Cependant, le pire des cas est O (n).

Answer 2

Je dirais encore qu'il est O (n) (ou au moins au pire O (n), à moins que votre index peut être fait moins de -1 dire -10, qui réinitialiser davantage)

Mais oui O (n).

Answer 3

O (n) où n est la longueur de la chaîne strippedText. Dans le pire des cas, chaque caractère sera égal à searchText et entraînera des n térations, mais même si ce n'est pas le cas (ce que je suppose que ce ne sera pas le cas), votre cas moyen sera un facteur, c, de n où c est supérieur à zéro mais inférieur à 1, donc le nombre de boucles sera cn, mais un facteur constant de n sera toujours représenté par O (n).

Answer 4

En fait c'est O (strippedText.Length * searchText.Length) puisque l'index de fait une comparaison entre les caractères dans searchText et strippedText.

Answer 5

Il est encore O(n) - c'est parce qu'il croît asymptotiquement au même rythme que O(n)

notation Big O est utilisé pour la limite supérieure de la croissance algorithmique - qui est, il est une fonction que l'algorithme est garanti croître au même rythme que, ou plus lentement que.

Dans le cas moyen, votre algorithme va croître au taux O(n/m) où m est une estimation de la densité des index dans vos chaînes (0 = pas d'index, 1 = indice à chaque caractère). En supposant que c'est à peu près constant sur n, vous pouvez ignorer le m et toujours dire que l'algorithme est O(n).

Le fait que, dans le monde réel, votre algorithme sera presque certainement plus rapide que O(n) ne l'arrête pas O(n) fonction.

---

Jetez un oeil à this page, en particulier:

Le symbole O est utilisé pour décrire une limite supérieure asymptotique pour la grandeur d'une fonction en termes d'une autre fonction plus simple. Cela signifie que pour x> k, lorsque x tend vers l'infini, la valeur f (x) sera toujours inférieure à C * g (x) (avec C a constante).

Answer 6

Je dirais que c'est O(n/m) où strippedText.Length == n et m est la longueur d'un préfixe de searchText qui est un suffixe de searchText (si aucune préfixe existe, il est la longueur de searchText).

Exemples:

searchText = 'ababab' -> m == 2

searchText = 'aaaaaa' -> m == 1

searchText = 'abcabc' -> m == 3

searchText = 'abcdefg' -> m == 7

Answer 7

tout dépend de la façon dont les chaînes méthode IndexOf() est mis en œuvre. Fondamentalement, il suffit de rechercher dans toute la chaîne avec IndexOf() - l'efficacité de cette méthode dépend de l'efficacité de cette méthode.

Il y a plusieurs string search algorithms de différentes complexités allant O(m+n)-O(m*n) (m et n étant la longueur des deux cordes).