« Complexité pratique contre complexité théorique » : différence entre les versions
Aucun résumé des modifications |
Aucun résumé des modifications |
||
| Ligne 4 : | Ligne 4 : | ||
La complexité en algorithmique sert à montrer l'efficacité d'un algorithme, en fonction de plusieurs facteurs comme son temps d'exécution, l'espace qu'il occupe dans la mémoire... (ces facteurs sont en générale induits par le nombre d'opérations qu'effectue l'algorithme). |
La complexité en algorithmique sert à montrer l'efficacité d'un algorithme, en fonction de plusieurs facteurs comme son temps d'exécution, l'espace qu'il occupe dans la mémoire... (ces facteurs sont en générale induits par le nombre d'opérations qu'effectue l'algorithme). |
||
Afin de mesurer et de représenter cette complexité, on représente l'évolution du temps d'exécution d'une même fonction en fonction de la taille de ses argument. |
Afin de mesurer et de représenter cette complexité, on représente l'évolution du temps d'exécution d'une même fonction en fonction de la taille de ses argument. |
||
On va donc, la plupart du temps utiliser des tableaux en entrée des fonctions et faire évoluer leurs taille |
On va donc, la plupart du temps utiliser des tableaux en entrée des fonctions, et faire évoluer leurs taille afin d'obtenir la courbe de leur complexité. |
||
Cette courbe va ainsi nous éclairer sur le comportement asymptotique de l'algorithme. Ce comportement asymptotique représente le comportement général de la fonction de la complexité (souvent impossible à calculer de manière exacte). Cette approximation est généralement représenté par O(f(n)), ou f(n) représente une fonction telle que $$1^Z $$ |
|||
| ⚫ | |||
pratique temps nb execution capacité a traiter information |
|||
à déterminer son comportement général |
|||
pratique |
|||
| ⚫ | |||
== Etudes d'algorithmes == |
== Etudes d'algorithmes == |
||
Afin de mesurer la complexité avec le langage python, on utilise généralement une fonction essentielle, la fonction "timeit" |
|||
<pre> |
<pre> |
||
import timeit |
import timeit |
||
def chronoquick(tab,nessais): |
def chronoquick(tab,nessais): |
||
'''Entrées: un tableau et un entier, Sortie: un entier''' |
'''Entrées: un tableau et un entier, Sortie: un entier''' |
||
Version du 5 mai 2021 à 14:20
Principe de la complexité
La complexité en algorithmique sert à montrer l'efficacité d'un algorithme, en fonction de plusieurs facteurs comme son temps d'exécution, l'espace qu'il occupe dans la mémoire... (ces facteurs sont en générale induits par le nombre d'opérations qu'effectue l'algorithme). Afin de mesurer et de représenter cette complexité, on représente l'évolution du temps d'exécution d'une même fonction en fonction de la taille de ses argument. On va donc, la plupart du temps utiliser des tableaux en entrée des fonctions, et faire évoluer leurs taille afin d'obtenir la courbe de leur complexité. Cette courbe va ainsi nous éclairer sur le comportement asymptotique de l'algorithme. Ce comportement asymptotique représente le comportement général de la fonction de la complexité (souvent impossible à calculer de manière exacte). Cette approximation est généralement représenté par O(f(n)), ou f(n) représente une fonction telle que $$1^Z $$
theorique forme infinie pratique temps nb execution capacité a traiter information
Etudes d'algorithmes
Afin de mesurer la complexité avec le langage python, on utilise généralement une fonction essentielle, la fonction "timeit"
import timeit
def chronoquick(tab,nessais):
'''Entrées: un tableau et un entier, Sortie: un entier'''
res = timeit.timeit("quickselectmed("+ str (tab)+")","from __main__ import quickselectmed" , number= nessais)
return res
dichotomie
tri de tableau: main/python
