En gros, on évalue la complexité d'un algorithme en regardant comment le tempts de calcul évolue en fonction de la taille des données.
- Si pour des données de taille n, l'algo nécessite 10 instructions, il est en temps constant.
- S'il nécessite x*n instructions, il est en temps linéaire.
- S'il nécessite n puissance x instructions, il est en temps polynomial.
- S'il nécessite x^n instructions, il est en temps exponentiel.
Toujours en résumant très grossièrement, on considère qu'un algo est "faisable en un temps raisonnable" s'il est polynomial de degré assez faible (n^2 c'est raisonnable, n^12 ça l'est déjà beaucoup moins) ou plus rapide que polynomial.
[^] # Re: 100 Ghz.....pour écrire son CV ?
Posté par Yusei (Mastodon) . En réponse au journal 100 Ghz.....pour écrire son CV ?. Évalué à 2.
- Si pour des données de taille n, l'algo nécessite 10 instructions, il est en temps constant.
- S'il nécessite x*n instructions, il est en temps linéaire.
- S'il nécessite n puissance x instructions, il est en temps polynomial.
- S'il nécessite x^n instructions, il est en temps exponentiel.
Toujours en résumant très grossièrement, on considère qu'un algo est "faisable en un temps raisonnable" s'il est polynomial de degré assez faible (n^2 c'est raisonnable, n^12 ça l'est déjà beaucoup moins) ou plus rapide que polynomial.