------------------------

Bonjour OPENCLASSROOM

   J'aimerais bien comprendre la notion de complexité.

   Pour ce faire, je suis tombé sur cet TD en ligne.
   Mes recherches sur Google m'ont permis de comprendre les fondamentaux. Cependant cet exercice me semble venu d'ailleurs ^_^.
Merci d'avance

Bonjour,

tu entends quoi par comprendre les fondamentaux ? Tu sais ce qu'une notation comme \(O(n \log n)\) signifie quand on parle de complexité temporelle de tris par comparaison  par exemple ?

Bonjour,

Oui je comprends très bien ces différentes notions...

Avec des amis, on a travaillé sur ce sujet. Seulement on a des divergences sur la reponse.

Un groupe trouve :  p1*p2

Un autre: p1+p2

Le dernier groupe : p1+p2 + 1

Je demande donc le point de vue de la communauté.

Merci d'avance :-)

Une réponse avec p1 ou p2 est forcément fausse. Il faut exprimer la complexité en fonction de la taille des données d'entrée, ici il s'agira de Taille1 et Taille2.

Il y a plusieurs approches. La première consiste à consiste à considérer les opérations mathématiques en temps constamt donc en O(1). La question à se poser est de savoir combien de fois on boucle. On remarque que les conditionnelles font soit progresser les indices soit simultanément soit l'un ou l'autre mais en les incrémentant de 1 à chaque fois. Donc dans le pire des cas  on ne sort de la boucle qu'après avoir parcouru tout T1 et tout T2. La complexité temporelle est donc en O(Taille1+Taille2).

Considérer les opérations mathématiques en temps constant est un peu cavalier, mais pas trop éloigné de la réalité dans un cours d'introduction.