Bonsoir,

J'ai plusieurs algorithmes à traiter mais je ne comprends pas comment faire.

Voici un des algorithmes :

A(x, y)
Début
i <- 1;
j <- 1;
quand (j <= y) faire
si (i <= x) alors
i <- i+1;
sinon
j <- j+1;
fin;
fin;
Fin;

Comment calculer T(x,y) ?
Je sais qu'il faut faire la somme des opérations élémentaires (multiplication, soustraction, test, etc..) mais j'ai un peu du mal à reconnaître certaines et je ne sais pas si par exemple l'affectation est une opération élémentaire.

Egalement, que faire lors d'une boucle ?

Bref, merci de votre lecture

J'ai à peu près compris l'algo mais quel est ce signe "<=" ? Est-ce que ce signe veut dire "plus petit ou égale que" ?
Et ensuite, qu'est-ce que la fonction T(x, y) ?

Alors :

<- est l'affection
<= est inférieur ou égal (dur à écrire ici)
T(x,y) est le temps de calcul de la fonction A(x,y)

C'est quoi "quand" ? C'est une nouvelle sorte de boucle inventée par les génies de la pédagogie actuelle ?

Si tu me dis ce que c'est et quelle est sa sémantique (ie, comment cette boucle se comporte), je pourrais t'aider.

Oui c'est étrange, c'est pourtant écrit cela noir sur blanc sur ma feuille.

Je pense que c'est un while...do

En anglais, ça donnerait donc :

A(x, y)
Begin
i <- 1;
j <- 1;
while (j <= y) do
if (i <= x) then
i <- i+1;
else
j <- j+1;
end;
end;
End;

Bon ben je pense avoir trouvé la réponse.

Je la partage ici au cas où quelqu'un aurait un problème semblable et utiliserait la fonction rechercher à l'avenir.
Néanmoins, c'est une hypothèse et non une affirmation, je n'ai pas encore eu la correction :

Il y a :
2 affectations au début
1 boucle (avec 1 test)
1 test (le if)
1 affectation ensuite
1 addition

Soit en tout, 2 opérations élémentaires + 4 dans la boucle.

T(m,n) = 4*x + 4*y + 2 + 1 = 4*x + 4*y + 3
Pourquoi 4, car on a 4 opérations x fois et 4 opérations y fois.
Pourquoi 2, car je compte les 2 affectations du début (constante).
Pourquoi 1, car une fois que y > j, on fait le test une dernière fois avant de s'arrêter car y > j (constante).

Soit D(x,y) = O(x + y)

C'est bien un O(x+y), mais ce n'est pas la peine de détailler autant le calcul, d'autant plus que ça n'a pas trop de sens de donner la même complexité à un test, une affectation et une addition. Ce que tu as écrit n'est pas faux en soi mais c'est lourd et maladroit

Ici typiquement, les affectations du début on s'en fout, et puis on voit qu'il y a un nombre constant d'opérations dans la boucle, on s'en fout de savoir si c'est 1 ou 4 ou 36.
Du coup, tu comptes juste le nombre d'exécutions de la boucle qui vont avoir lieu.
Pendant les x premières passes tu vas incrémenter i, puis la condition i <= x ne sera plus vérifiée, et du coup tu vas te mettre à incrémenter j pendant y passes.
La complexité est bien du O(x+y)

Bonjour

Inutile d'écrire ton algorithme en anglais, un algorithme s'écrit dans la langue commune, ici le français, et n'a de forme que celle qui soit le plus compréhensible possible sans connotation aucune a un language précis.

Moi je dirais 7 car on ne compte pas le nombre de foi ou l'algorithme tourne (car on en connais pas x), c'est donc le nombre opération qui sont écrite donc 4 affectation et 3 tests.

Le but n'etait pas de l'ecrire en anglais mais de corriger ce "quand" qui ne veut franchement rien dire.

papy386, on ne connait jamais x, c'est tout le but du calcul de complexite, d'etudier le cout de l'operation quand les parametres varient.

L'analyze de cavalieranal est la bonne. Ici, il y a 2 operations avant la boucle et 3 operations dans la boucle (2 tests, une addition). Il y a exactement x+y tours de boucle. Donc au plus 2 + 3(x+y) operations. Ce qui fait que c'est dans O(x+y).

faudrait remplacer le QUAND par TANT QUE

Bonjour et merci de votre réponse.

Le prof avait déjà fait un exercice sur la complexité et nous a donné un corrigé, ensuite c'était "débrouillez vous" sans qu'on ai eu un seul cours dessus.

Sinon je suis d'accord pour dire qu'on s'en fiche des constantes et que seul O(x+y) est intéressant, je viens de le voir hier en cours. Néanmoins, sur le coup, je ne savais pas ça et j'ai détaillé exactement comme le prof (bien que son corrigé de cours n'avait ni boucle ni condition ni affectation).

En tout cas, merci de votre réponse !

C'est bien de détailler trop que pas assez, au début Après t'auras l'habitude de voir au premier coup d'oeil ce qui est important ou non et tu verras que c'est du O(x+y) sans faire le moindre calcul