^{PDFprof.com Search Engine}

Complexité algorithmique

Qu'est-ce que la complexité algorithmique ?
La complexité algorithmique est un concept très important qui permet de comparer les algorithmes afin de trouver celui qui est le plus efficace. Il existe une notation standard qui s’appelle big O et qui permet de mesurer la performance d’un algorithme. Vous verrez, au fur et à mesure des explications, la méthode de calcul.
Comment calculer la complexité d’un algorithme ?
Il est plus difficile de calculer la complexité de cet algorithme car il est récursif : la complexité de Fibo dé- pend. . . de la complexité de Fibo ! Définissons alors Cn comme étant le nombre d’opérations nécessaire pour calculer Fibo(n). On peut écrire la formule suivante : Cn Op1q Cn 1 Cn 2.
Quelle est la complexité temporelle de notre algorithme ?
Si l’on note n le nombre de chiffres de notre cadenas, le temps de calcul est donc 10n ; ainsi, à l’aide de la notion big O, nous pouvons noter que la complexité temporelle de notre algorithme est de O ( 10n). On dit alors que la complexité est exponentielle.
Qu'est-ce que la théorie de la complexité ?
La théorie de la complexité est le domaine des mathématiques, et plus précisément de l' informatique théorique, qui étudie formellement le temps de calcul, l'espace mémoire (et plus marginalement la taille d'un circuit, le nombre de processeurs, l'énergie consommée…) requis par un algorithme pour résoudre un problème algorithmique.

Qu'est-ce que la complexité algorithmique ?