Discussion :

[direct]

Salut tous le monde,
Je veux savoir la complexité de ma solution pour ce petit exercice qui dit :
On veut ecrire une fonction "existe" qui retourne 1 si une chaine de caractère est à la fin de l'autre et 0 dans le cas contraire.
Par exemple :
CH1=> "Bonjours"
CH2=> "jours"
==> Elle retourne (1)
et (0) dans le cas contraire.

Ce que je veux savoir c'est le calcul analytique de la complexité de ma fonction qui suit : (Je vais l'écrire en langage C) si ça ne vous dérange pas :

Code C :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
int finChaine (char *s, char *t)
{
char *p1, *p2;
int ok;
//Initialisation 
p1 = s + strlen(s);
p2 = t + strlen(t);
ok = 1; /*Vrai*/
 
   while (ok)
   {
   p1--;
   p2--;
      if (!(*p1 == *p2 && p2 > t))
      {
       ok = 0;
       break;
       }
   }
}

Concernant le nom de la fonction c'est le prototype proposé par l'exercice si vous parlera de la lisibilité. Et Merci en tout cas.

[ToTo13]

Bonjour,

tu parcours qu'une seule fois ta chaîne de caractère, donc complexité linéaire en fonction du nombre de caractère.

[direct]

Alors c'est juste ce que j'ai dit dans tête merci Mr à la prochaine O(strlen(t))