Complexité algorithme

[manynho430]

Bonjour, je bloque sur un exercice dont voici l'énoncé :

L’algorithme 4 recherche si un vecteur binaire (composé de 0 et de 1) contient le motif 111. Calculez
la complexité moyenne (en nombre de comparaisons), en considérant que le motif est dans le vecteur
avec une probabilité q et que dans ce cas, toutes les positions de première apparition du motif sont
équiprobables. Vos calculs devront être clairement expliqués.

Algorithme 4 : Recherche d’un motif dans un vecteur binaire
début
/* ENTRÉES : Un vecteur de binaires V de taille n ≥ 3 */
/* SORTIE : indique la présence du motif 111 dans le vecteur */
rep ← Faux ; i ← 1
tant que i < n−1 faire
si V(i) = 1 et V(i+1) = 1 et V(i+2) = 1 alors rep ← vrai ; i ← n
sinon i ← i+1
retourner rep
fin

On prend le cas ou il n'y a pas le motif, du coup on va faire 3 comparaisons par itération jusqu'à n-2 de ce fait c(pas inclus) = 3(n-2).
Cmoy(pas inclus)=3(n-2)*(1-q)
Pour le cas ou il est inclus je suis pas sur je bloque ici, voici que je pense:
pour moi comme la position est équiprobable donc la probabilité pour que le motif sois inclus et sa premiere position est donc de 1/n ?
on devra faire 3+3*j comparaisons si on appelle j le rang qui valide les tests.

Mais je suis bloqué ici car j'ai l'intuition que c'est pas le bon raisonnement

Merci pour votre aide

[Ben314]

Salut,
Si, c'est bon, modulo que ta proba. de 1/n pour qu'il y ait 111 dés le début, c'est pas tout à fait ça :
- Déjà, des "position de première apparition" (dixit l'énoncé), il n'y en a pas n, mais n-2.
- Ensuite, l'équiprobabilité a lieu au cas où le motif soit effectivement présent, donc c'est une proba conditionnelle et la vrai proba. que le motif soit situé à une position donnée, c'est q/(n-2).

Ensuite, il y a une proba. de q/(n-2) que le motif soit à la première position, donc qu'il y ait exactement 3 comparaisons ; il y a une proba. de q/(n-2) que le motif soit à la deuxième position, donc qu'il y ait exactement 6 comparaisons ; il y a une proba. de q/(n-2) que le motif soit à la troisième position, donc qu'il y ait exactement 9 comparaisons ; etc etc ; et à la fin, il y a une proba. de q/(n-2) que le motif soit à la fin, donc qu'il y ait exactement 3(n-2) comparaisons (comme dans le cas où le motif est absent).

Et si tu somme tout ça, ça fait . . .

[manynho430]

Salut,
Si, c'est bon, modulo que ta proba. de 1/n pour qu'il y ait 111 dés le début, c'est pas tout à fait ça :
- Déjà, des "position de première apparition" (dixit l'énoncé), il n'y en a pas n, mais n-2.
- Ensuite, l'équiprobabilité a lieu au cas où le motif soit effectivement présent, donc c'est une proba conditionnelle et la vrai proba. que le motif soit situé à une position donnée, c'est q/(n-2).

Ensuite, il y a une proba. de q/(n-2) que le motif soit à la première position, donc qu'il y ait exactement 3 comparaisons ; il y a une proba. de q/(n-2) que le motif soit à la deuxième position, donc qu'il y ait exactement 6 comparaisons ; il y a une proba. de q/(n-2) que le motif soit à la troisième position, donc qu'il y ait exactement 9 comparaisons ; etc etc ; et à la fin, il y a une proba. de q/(n-2) que le motif soit à la fin, donc qu'il y ait exactement 3(n-2) comparaisons (comme dans le cas où le motif est absent).

Et si tu somme tout ça, ça fait . . .

D'accord, je vois donc on somme le tout ça fait somme de 3*j allant j=1 à n-2, ça donne (3*(n-2)*(n-1))/2.

On en déduit la complexité moyenne dans le cas ou le motif est inclus est de (3*(n-1)*q)/2) et dans le cas ou il n'est pas inclus 3(n-2)*(1-q) c'est bien ça ?