[PDF] [PDF] Complexité (tri à bulle) - limsi

View - Download [PDF] Complexité (tri à bulle) - limsi

Previous PDF

Next PDF

Complexité

Complexité (tri à bulle)

Patrick Paroubek

LIMSI-CNRS

Dépt. CHM - Groupe ILES

Bât. 508 Université Paris Sud, 91403 Orsay Cedex pap@limsi.fr lundi 15 janvier 2018 / M2 / Programmation iérative/récursive - Cours S2-1

Patrick ParoubekComplexité

ComplexitéDéfinition

Tri à bulle

V0 : la fonction identitéLa complexité d"un algorithme est la fonction mathématique qui décrit en fonction de la taille des données d"entrées (par exemple le nombre de mots), soit la taille mémoire utilisée, soit le temps de calcul nécessaire à la production du résultat final. La complexité mémoire est exprimée en nombre de cellules mémoire ou en octets, la complexité est exprimée en fonction du nombre d"instruction de base du processeur (.e.g. addition de 1, déplacement d"une zone mémoire). Par ex. la complexité de la recherche d"un noeud quelconque dans un arbre binaire comprenant n noeuds est :nlog(n).Patrick ParoubekComplexité

ComplexitéDéfinition

Tri à bulle

V0 : la fonction identitéPour visualiser les courbes mathématiques vous pouvez utiliser le logiciel gratuit geogebra (niveau collège) https://www.geogebra.org/?lang=fr

Patrick ParoubekComplexité

ComplexitéDéfinition

Tri à bulle

V0 : la fonction identitéPour les calculs de complexité, nous ne sommes pas intéressés par la valeur exacte de la ressource consommée (mémoire ou instructions de calcul), mais par la famille de fonction à laquelle appartient la fonction de complexité (logarithmique, linéaire, quadratique, de degré 3, 4, ..., exponentielle). Evidemment plus cette complexité est basse plus le temps de calcul sera court, ou bien plus l"espace mémoire nécessaire au programme sera petit.

Patrick ParoubekComplexité

ComplexitéDéfinition

Tri à bulle

V0 : la fonction identitéRappels :

monôme axb;a2R;b2N polynôme a

0xb0+a1xb1+::: :::+akxbk;ai2R;bi2N;k2N

exponentielle abx;a2R;b2RPatrick ParoubekComplexité

ComplexitéDéfinition

Tri à bulle

V0 : la fonction identitéOn distingue deux classes d"algorithmes, ceux de la classe P, qui sont déterministes s"exécutent en un temps polynomiale et ceux de la class NP, qui sont non-déterministes et qui s"exécutent en temps polynomial. Ceux de la classe P sont considérés comme de bons algorithmes (temps de calcul raisonnable), ceux de la classe NP sont problématiques voire impossibles, dès que les données d"entrée ont une certaine taille.

Patrick ParoubekComplexité

ComplexitéDéfinition

Tri à bulle

V0 : la fonction identitéPour tout algorithme, on peut toujours échanger du temps pour de l"espace et vice-versa. C"est-à-dire que l"on peut obtenir un temps de calcul plus court si l"on consomme plus de mémoire (par ex. en stockant des résultats intermédiaires qui seront réutilisés sans avoir à les recalculer), ou bien un algorithme occupant un espace mémoire plus petit, mais au prix d"un temps de calcul plus long.

Patrick ParoubekComplexité

ComplexitéDéfinition

Tri à bulle

V0 : la fonction identitéLa notationO()(dite notation de Landau) beaucoup utilisée en complexité des algorithmes

Considérons la fonctiong:N!R

et l"ensemble des fonctionsf()défini comme suit :

O(g(n)) =ff:N!R(1)

j 9c>0^n0>0(2) j0f(n)c:g(n);8nn0(3) g(4)Patrick ParoubekComplexité

ComplexitéDéfinition

Tri à bulle

V0 : la fonction identitéSi pour une fonctionh(n)nous écrivonsh(n) =O(g(n)), cela signifie que l"ensemble des fonctionsO(g(n))est la borne supérieure asymptotique deh(n). Intuitivement, dès que n devient suffisamment grand, les deux courbes h(n) et g(n) se comportent de manière similaire à une constante près.

Patrick ParoubekComplexité

ComplexitéDéfinition

Tri à bulle

V0 : la fonction identitéOrdres de grandeur

complexité efficaces,

POL YNOMIALES

de deg rémaxim um <1, 2, 3, ..., 6 mais rarement au delà (essentiellement<2 ou 3)ce qu"on neVEUT P AS: une comple xitée xponentielle, carO(cn);c>1, par exemple sin=2, pour une taille de problème den=100 (ce qui est très petit), nous aurons une complexité de 2

1001030, c"est à dire environ

31011siècles si on considère qu"il s"agit d"une

complexité en temps et qu"une opération prend une nanoseconde!

Patrick ParoubekComplexité

ComplexitéDéfinition

Tri à bulle

V0 : la fonction identitéProgrammer en Python de manière récursive et itérative le tri à

bulles d"une liste de nombres entiers.

Rappel principe du tri à bulles :on parcourt la liste à trier du début à la fin, lorsque l"on

rencontre deux éléments consécutifs qui ne sont pas dans l"ordre, on les permutesi l"on parcourt la liste sans rencontrer d"éléments consécutifs en désordre, alors la liste est triée.

Patrick ParoubekComplexité

ComplexitéDéfinition

Tri à bulle

V0 : la fonction identitéLes objets mis en jeu : la liste la position de l"élément que l"on compare à son successeur

Patrick ParoubekComplexité

ComplexitéDéfinition

Tri à bulle

V0 : la fonction identitéV0 : programmer la fonction identité

Patrick ParoubekComplexité

quotesdbs_dbs7.pdfusesText_5

[PDF] algorithme de tri par fusion

[PDF] algorithme de tri par insertion

[PDF] algorithme de tri par insertion d'un tableau

[PDF] algorithme de tri par insertion dichotomique

[PDF] algorithme de tri par insertion en c

[PDF] algorithme de tri par insertion en langage c

[PDF] algorithme de tri par insertion java

[PDF] algorithme de tri par insertion pdf

[PDF] algorithme de tri par sélection

[PDF] algorithme de tri par selection en c

[PDF] algorithme de tri par selection java

[PDF] algorithme de tri par selection pdf

[PDF] algorithme de tri par selection recursive

[PDF] algorithme de tri pdf

[PDF] algorithme de tri rapide