Metraipolis › archive › dc_76f17378fcd3
Complexité d'un algorithme — Wikipedia (fr)
- Source
- Wikipedia (fr)
- Original
- https://fr.wikipedia.org/wiki/Complexit%C3%A9_d%27un_algorithme
- License (as archived)
- CC-BY-SA-4.0
- Archived
- 2026-11-05T09:44:29.051Z
- SHA-256 of the archived text
63f47530fc3fde27df394ea5a70cc5492ab2fe562a5612553987517d0ea532ec- Stable URL of this page
https://metraipolis.com/documento/dc_76f17378fcd3
How to cite
Complexité d'un algorithme — Wikipedia (fr) — Wikipedia (fr), https://fr.wikipedia.org/wiki/Complexit%C3%A9_d%27un_algorithme (CC-BY-SA-4.0); archived copy: https://metraipolis.com/documento/dc_76f17378fcd3 (Metraipolis archive dc_76f17378fcd3, sha256 63f47530fc3fde27df394ea5a70cc5492ab2fe562a5612553987517d0ea532ec)
BibTeX
@misc{dc76f17378fcd3,
title = {Complexité d'un algorithme — Wikipedia (fr)},
howpublished = {Wikipedia (fr)},
url = {https://fr.wikipedia.org/wiki/Complexit%C3%A9_d%27un_algorithme},
note = {License CC-BY-SA-4.0; archived copy https://metraipolis.com/documento/dc_76f17378fcd3; sha256 63f47530fc3fde27df394ea5a70cc5492ab2fe562a5612553987517d0ea532ec},
year = {2026}
}Archived text
Reproduced under CC-BY-SA-4.0. Attribution: Wikipedia (fr), https://fr.wikipedia.org/wiki/Complexit%C3%A9_d%27un_algorithme. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
En informatique, la complexité algorithmique, ou complexité de calcul, d'un algorithme correspond à la quantité de ressources nécessaires à son exécution. On s'intéresse particulièrement au temps de calcul (généralement mesuré par le nombre d'opérations élémentaires requises) et aux besoins en mémoire. La complexité d'un problème est associée à la complexité des meilleurs algorithmes permettant de le résoudre. L'étude de la complexité des algorithmes explicitement définis est appelée analyse des algorithmes, tandis que l'étude de la complexité des problèmes est appelée théorie de la complexité algorithmique. Ces deux domaines sont étroitement liés, car la complexité d'un algorithme constitue toujours une borne supérieure de la complexité du problème qu'il résout. De plus, la conception d'algorithmes dits efficaces, repose sur la comparaison la complexité de l'algorithme proposé à celle du problème à résoudre. D'autre part, dans la plupart des cas, la seule information connue concernant la complexité d'un problème est qu'elle est inférieure à celle des algorithmes les plus efficaces connus capables de résoudre le problème. Il existe donc une superposition significative entre l'analyse des algorithmes et la théorie de la complexité. Comme la quantité de ressources nécessaires à l'exécution d'un algorithme varie généralement avec la taille de l'entrée, sa complexité est le plus souvent exprimée par une fonction n → f(n), où n représente la taille de l'entrée et f(n) soit la complexité dans le pire des cas (la quantité maximale de ressources nécessaires pour toutes les entrées de taille n ), soit la complexité moyenne (la moyenne des ressources nécessaires pour les entrées de taille n ). La complexité temporelle est généralement exprimée comme le nombre d'opérations considérées élémentaires qui sont requises pour l'exécution sur une entrée de taille n. Ces opérations étant supposées avoir une durée d'exécution constante sur un ordinateur donné et ne varier que d'un facteur constant lorsqu'elles sont exécutées sur une autre machine. La complexité spatiale est généralement exprimée comme la quantité de mémoire requise par un algorithme pour une entrée de taille n . Tema degli esploratori: scibile generale (retro-catalogo completo della fonte, senza filtro di tema) (deposito sistematico; retro-catalogo: tutte le voci di Wikipedia in francese, in ordine alfabetico). Fonte: Wikipedia in francese, voce «Complexité d'un algorithme» — https://fr.wikipedia.org/wiki/Complexit%C3%A9_d%27un_algorithme Wikidata Q5157286: «misura della quantità di risorse intrinsecamente necessarie per eseguire un algoritmo che risolva un problema computazionale» (dati Wikidata in CC0 1.0) — https://www.wikidata.org/wiki/Q5157286 Autori: i contributori di Wikipedia (cronologia: https://fr.wikipedia.org/wiki/Complexit%C3%A9_d%27un_algorithme?action=history). Licenza: Creative Commons Attribuzione-Condividi allo stesso modo 4.0 (CC BY-SA 4.0) — https://creativecommons.org/licenses/by-sa/4.0/. Il riuso richiede attribuzione e stessa licenza. Estratto dell'introduzione non modificato nel contenuto; revisione 240603691, consultata il 2026-11-05T09:40:14.756Z tramite l'API ufficiale di Wikipedia. Impronta SHA-256 dell'estratto: 3782a1b76e8fbad713fcce2d63006c6fceb1df409a0d9bda56c251892dd69e77