^{PDFprof.com Search Engine}

Algorithmique et complexité

Quelle est la complexité d'un algorithme ?
La complexité algorithmique de la seconde est logarithmique alors que celle de la première est linéaire. L' analyse de la complexité d'un algorithme consiste en l'étude formelle de la quantité de ressources (par exemple de temps ou d' espace) nécessaire à l'exécution de cet algorithme.
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.
Quelle est la théorie de la complexité?
La théorie de la complexité a commencé en adaptant les méthodes de la calculabilité au cas du temps de calcul borné. Par exemple, on retrouve de nombreux ingrédients issus de la calculabilité dans la démonstration du théorème 3-AK de Ladner datant de 1975.
Comment classer les algorithmes en fonction de leur temps d'exécution ?
On s'intéresse alors au comportement asymptotique de cette mesure en fonction de la taille des données passées à l'algorithme. On définit donc des ordres de grandeur, nous permettant de classer des algorithmes en fonction de leur temps d'exécution.

Quelle est la complexité d'un algorithme ?