^{PDFprof.com Search Engine}

Chapitre 8 : Complexité

Comment calculer la complexité d'un programme ?
La complexité linéaire
Sa technique est simple : il tourne la molette du premier chiffre jusqu'à entendre un "clic".
Il sait alors que le chiffre est bon et passe au suivant.
Il peut donc trouver les bons chiffres un par un, sans avoir à se soucier des autres.
Comment déterminer la complexité d'une fonction ?
La complexité en temps d'un algorithme sera exprimé par une fonction, notée T (pour Time), qui dépend : de la taille des données passées en paramètres : plus ces données seront volumineuses, plus il faudra d'opérations élémentaires pour les traiter.
On notera n le nombre de données à traiter.
Comment calculer la complexité en espace ?
On définit la fonction de complexité en espace s_M de M de la manière suivante. s_M(n) = max_w₌_n s_M(w).
La valeur s_M(n) représente l'espace maximal d'un calcul de M avec une entrée de taille n.
Réponse algorithmique
Pour mesurer le temps d'exécution d'un algorithme, on définit la complexité en temps qui représente le nombre d'étapes qui sont nécessaires pour résoudre le problème pour une entrée de taille donnée.

La complexité est donc O(n2), c'est-à-dire quadratique. Pour la fonction deuxfor2, on effectue : • 2 affectations,. • une boucle for de longueur n avec, à Autres questions

Chapitre 8 : Complexité

Comment calculer la complexité d'un programme ?

Comment déterminer la complexité d'une fonction ?

Comment calculer la complexité en espace ?