human
Veuillez expliquer ce qu'est la "complexité de calcul"
gpt
En informatique, la complexité de calcul ou simplement la complexité d'un algorithme est la quantité de ressources nécessaires pour l'exécuter. Une attention particulière est accordée au temps de calcul (généralement mesuré par le nombre d'opérations élémentaires nécessaires) et aux besoins en stockage mémoire. La complexité d'un problème est la complexité des meilleurs algorithmes permettant de résoudre le problème.
L'étude de la complexité d'algorithmes explicitement donnés est appelée analyse d'algorithmes, tandis que l'étude de la complexité de problèmes est appelée théorie de la complexité computationnelle. Les deux domaines sont étroitement liés, car la complexité d'un algorithme est toujours une limite supérieure à la complexité du problème résolu par cet algorithme. De plus, pour concevoir des algorithmes efficaces, il est souvent fondamental de comparer la complexité d'un algorithme spécifique à la complexité du problème à résoudre. De plus, dans la plupart des cas, la seule chose connue sur la complexité d'un problème est qu'elle est inférieure à la complexité des algorithmes connus les plus efficaces. Par conséquent, il existe un grand chevauchement entre l'analyse des algorithmes et la théorie de la complexité.
Comme la quantité de ressources nécessaires pour exécuter un algorithme varie généralement avec la taille de l'entrée, la complexité est généralement exprimée sous la forme d'une fonction n → f(n), où n est la taille de l'entrée et f(n) est soit la la complexité du pire cas (le maximum de la quantité de ressources nécessaires sur toutes les entrées de taille n) ou la complexité du cas moyen (la moyenne de la quantité de ressources sur toutes les entrées de taille n). La complexité temporelle est généralement exprimée comme le nombre d'opérations élémentaires requises sur une entrée de taille n, où les opérations élémentaires sont supposées prendre un temps constant sur un ordinateur donné et ne changent que d'un facteur constant lorsqu'elles sont exécutées sur un ordinateur différent. La complexité spatiale est généralement exprimée comme la quantité de mémoire requise par un algorithme sur une entrée de taille n.