[PDF] Complexité (tri à bulle) La complexité d'un algorithme

View - Download Complexité (tri à bulle)

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é

ComplexitéDéfinition

Tri à bulle

V0 : la fonction identité#!/usr/bin/env python

# -*- coding: utf-8 -*- # Version 0 , lecture des données dans un fichier et écriture # des données à l"identique dans un fichier # Documenter la commande d"appel avec un exemple des arguments # à fournir, usage : # test_numbers.txt = fichier contenant des nombre entier séparés # par des espaces. Il peut y avoir plusieurs # lignes de chiffres. # result_numbers.txt = fichier ou la sortie produite est sauvegardée. # > python bubble_sort_v0.py -i test_numbers.txt -o result_numbers.txt import sys import io import re import codecsPatrick ParoubekComplexité

ComplexitéDéfinition

Tri à bulle

V0 : la fonction identité#------------------------------------------------------------ # lecture des parametres de la commande bash if len(sys.argv) < 4: print("A Usage is: word_lister -i in_path -o out_path") exit() i=1 while i < 4: if sys.argv[i] == "-i": in_path = sys.argv[ i+1 ] i += 2 else: if sys.argv[i] == "-o": out_path = sys.argv[ i+1 ] i += 2 else: print("B Usage is: word_lister -i in_path -o out_path") exit() # ouverture des flux d"entrée et de sortie in_strm = codecs.open(in_path, mode="r", encoding="utf-8") out_strm = codecs.open(out_path, mode="w", encoding="utf-8")Patrick ParoubekComplexité

ComplexitéDéfinition

Tri à bulle

V0 : la fonction identité#--------------------------------------------------------------------------------

# Les nombres à traiter sont lus et rangés dans la variable all_nbrs all_nbrs = [] for line in in_strm: for val in line.split(): all_nbrs.append( int( val ) ) # Écriture de la sortie (les nombres à traiter) dans le fichier de sortie. out_strm.write( "list of numbers to sort= [" ) firstp = bool(1) for k in all_nbrs: if firstp: firstp = bool(0) else: out_strm.write( ", " ) out_strm.write( str(k) ) out_strm.write( "]\n" ) #----- c"est fini! -----Patrick ParoubekComplexité

ComplexitéDéfinition

Tri à bulle

V0 : la fonction identitéRemonter toutes les bulles d"une position si nécessaire

Patrick ParoubekComplexité

ComplexitéDéfinition

Tri à bulle

V0 : la fonction identité#--------------------------------------------------------------------------------

# le tri itératif # effectue une exploration de la liste a partir du début et retourne vrai # (il reste du tri) si des nombres ont été permutés et faux sinon. def move_one_bubble( l ): if( (len(l) == 0) or (len(l) == 1) ): return bool(0) else: max_i = (len(l) - 1) b = bool( 0 ) for i in range(0, max_i): out_strm.write( "move_one_bubble_loop i= " ) out_strm.write( str(i) ); out_strm.write( " bool= " ) out_strm.write( str(b) ); out_strm.write( "\n" ) if( l[i] > l[i+1] ): out_strm.write( "switching " ); out_strm.write( str(l[i]) ) out_strm.write( " and " ); out_strm.write( str(l[i+1]) ) out_strm.write( "\n" ) aux = l[i+1] l[i+1] = l[i] l[i] = aux b = bool( 1 ) return bPatrick ParoubekComplexité

ComplexitéDéfinition

Tri à bulle

V0 : la fonction identitéRemonter toutes les bulles au maximum def move_all_bubbles( l ): out_strm.write( "----- move_all_bubbles ---------\n" ) while( move_one_bubble( l ) ): out_strm.write( "----- move_one_bubble iteration ---------\n" ) return l move_all_bubbles( all_nbrs )

Patrick ParoubekComplexité

ComplexitéDéfinition

Tri à bulle

V0 : la fonction identitéLa complexité en temps (nombre d"opérations) du tri à bulles estO(cn2) donc au maximum le carré de la taille de la liste à trier (modulo le produit par une constante).

Patrick ParoubekComplexité

quotesdbs_dbs21.pdfusesText_27

[PDF] algorithme tri par selection python

[PDF] algorithmic bias in recruitment

[PDF] algorithmique et programmation c

[PDF] algorithmique et programmation en java cours et exercices corrigés pdf

[PDF] algorithmique et programmation en pascal

[PDF] algorithmique et programmation en pascal (résumé)

[PDF] algorithmique et programmation en pascal exercices corriges

[PDF] algorithmique et programmation python

[PDF] algorithmique programmation et complexité lyon 1

[PDF] algorithms with c o'reilly pdf

[PDF] alibaba business model pdf

[PDF] alibaba competitive advantage

[PDF] alibaba presentation

[PDF] alienware aw3418dw displayport not working

[PDF] aliera healthcare payer id