Complexité Temps

[invite238d83df]

Bonjour,

Pouvez-vous m'expliquer ce qu’est la complexité Temps au sens « plus mauvais cas » d’un algorithme A, qui calcule une sortie O de type Output à partir d’une entrée I de type Input?

Merci
-----

[indian58]

Il s'agit du temps que prendra l'algorithme à s'exécuter dans le pire des cas.

[invite238d83df]

Merci.tu peux me donner un example?

[invite238d83df]

Exmple:

Input:un nombre n entier>1
Output: n est-il premier?
Algo:On tente la division pour tous les nombres entre 2 et [n+2]

[A voir en vidéo sur Futura]

[indian58]

Exmple:

Input:un nombre n entier>1
Output: n est-il premier?
Algo:On tente la division pour tous les nombres entre 2 et [n+2]

Si n est premier, ta complexité est la pire et vaut racine(n).

[invite238d83df]

tu peux me donner un exemple?

[indian58]

tu peux me donner un exemple?

??? n = 109

[invite238d83df]

tu peux me donner un example?

[indian58]

Euh, je vois pas ce que tu veux là.

[invite238d83df]

je veux un example pour m'expliquer ce qu’est la complexité Temps au sens « plus mauvais cas » d’un algorithme A, qui calcule une sortie O de type Output à partir d’une entrée I de type Input?

[invite238d83df]

Merci beaucoup!

[indian58]

Tu l'as toi-même donné avec tes nombres premiers. S'il n'est pas premier, tu ne vas pas mettre longtemps à terminer l'algo. Tandis que s'il est premier, il te faudra racine (n).