Complexité algorithmique
9 sept. 2021 le cas de boucles imbriquées on calculera d'abord la complexité de la boucle interne car on en a besoin pour.
Complexité dun algorithme
Il comprend deux boucles imbriquées chacune effectuant n répétitions de son corps ; le corps de la boucle interne ne comporte qu'une multiplication.
Complexité
4. de la complexité en temps de l'algorithme «abstrait» sous-jacent. Théorème 1 La complexité de p boucles imbriquées de 1 à n ne contenant que.
Complexité algorithmique
Exemple : algorithmes avec deux boucles imbriquées. Tris à bulle par insertion et par sélection. O(ni) : complexité polynomiale
Complexité dun algorithme I Généralités
) ? 2n. Comme l'instruction x += 1 de la boucle en j est réalisée en O(1) la complexité temporelle dans le pire des cas des boucles imbriquées sur i et j est
1. BOUCLES ET COMPLEXITE
BOUCLES ET COMPLEXITE. A. Le langage de programmation Java. Java est un langage de programmation normalisé. Le mot Java est une marque déposée par la firme
Complexité des Algorithmes A) Introduction
Ce que l'on entend par complexité des algorithmes est une évaluation du coût Exemple-4 (deux boucles imbriquées sans dépendance des indices).
Algorithmique Notion de complexité
complexité temporelle : (ou en temps) : temps de calcul ; La complexité (théorique) est un ordre de grandeur de ces ... Cas des boucles imbriquées.
Jointures par boucles imbriquées
Si une table tient en mémoire : jointure par boucle imbriquées ou hachage. • Si au moins un index est utilisable : jointure par boucle imbriquées indexée.
Algorithmique Notion de complexité
complexité temporelle : (ou en temps) : temps de calcul ; La complexité (théorique) est un ordre de grandeur de ces ... Cas des boucles imbriquées.
[PDF] Complexité algorithmique - Université Grenoble Alpes
Comme établi précédemment pour une boucle on fait la somme des complexités de chaque itération Dans le cas de boucles imbriquées on calculera d'abord la
[PDF] Complexité dun algorithme I Généralités
La complexité temporelle des boucles imbriquées est donc en O(n2) Par somme la complexité temporelle dans le pire des cas de la fonction f1 est en O(n2) Q2
[PDF] Complexité algorithmique - MIS
O(ni) : complexité polynomiale quand le paramètre double le temps d'exécution est multiplié par 2i Exemple : algorithme utilisant i boucles imbriquées O(in)
[PDF] Calculs de complexité dalgorithmes
?Complexité des algorithmes ?Exemples de calcul de complexité boucles for imbriquées chacune d'elle de la forme for (int i
[PDF] Complexité des Algorithmes A) Introduction - LIPN
Ce que l'on entend par complexité des algorithmes est une évaluation du coût Exemple-4 (deux boucles imbriquées sans dépendance des indices)
[PDF] Complexité dun algorithme - Alexandre Benoit
Il comprend deux boucles imbriquées chacune effectuant n répétitions de son corps ; le corps de la boucle interne ne comporte qu'une multiplication
[PDF] TP 3 : Boucles et boucles imbriquées I Rappels
Et par exemple d'augmenter de 10 l'indice de la suite multiplie environ par 100 le temps de calcul Exercice 11 Évaluer la complexité des algorithmes
[PDF] 1 BOUCLES ET COMPLEXITE
BOUCLES ET COMPLEXITE A Le langage de programmation Java Java est un langage de programmation normalisé Le mot Java est une marque déposée par la firme
[PDF] Exemples de boucles imbriquées
boucle ? ou : on parle de boucles imbriquées (la 1e boucle est dite Commenté [AM1]: Nous disons que la complexité de cet
[PDF] Complexité des algorithmes - Pr Abdelhamid Djeffal
On cherche à mesurer la complexité d'un algorithme indépendamment de la La complexité d'une boucle est égale à la somme sur toutes les itérations de la
Comment mesurer la complexité ?
Réaliser un calcul de complexité en temps revient à compter le nombre d'opérations élémentaires (affectation, calcul arithmétique ou logique, comparaison…) effectuées par l'algorithme.Comment déterminer la complexité d'un algorithme ?
Pour calculer la complexité d'un algorithme: On calcule la complexité de chaque partie de l'algorithme. On combine ces complexités conformément aux règles déjà vues. On effectue sur le résultat les simplifications possibles déjà vues.Comment déterminer la complexité d'une fonction ?
On mesure alors la complexité en temps d'un algorithme comme le nombre de ces opérations élémentaires. Par exemple, en considérant élémentaire l'addition de 2 chiffres, poser l'addition de deux nombres de n chiffres nous fera effectuer n additions à 1 chiffre, la complexité sera donc de n.- ? La complexité d'un algorithme est la quantité de ressources nécessaires pour traiter des entrées. On la voit comme une fonction de n, la taille de l'entrée. ? Les principales ressources mesurées sont le temps (nombre d'instructions utilisées) et l'espace (quantité d'espace mémoire nécessaire).
Algorithmique...
Complexité
Luc Brun
luc.brun@greyc.ensicaen.frA partir de travaux de
Habib Abdulrab(Insa de Rouen)
Complexit
´e - p.1/25
Plan...
Notion de complexitéComment évaluer la complexité d'un algorithmeExemple de calculs de complexité
Complexit
´e - p.2/25
Notion de complexité (1)
Comment évaluer les performances d'un algorithmedifférents algorithmes ont des coûts différents en termes de
temps d'exécution (nombre d'opérations effectuées par l'algorithme),taille mémoire (taille nécessaire pour stocker les différentes structures de
données pour l'exécution). Ces deux concepts sont appelé la complexité en temps et en espace de l'algorithme.Complexit
´e - p.3/25
Notion de complexité (2)
La complexité algorithmique permet de mesurer les performances d'un algorithme et de le comparer avec d'autres algorithmes réalisant les mêmefonctionnalités.La complexité algorithmique est un concept fondamental pour toutinformaticien, elle permet de déterminer si un algorithmeaet meilleur
qu'un algorithmebet s'il est optimal ou s'il ne doit pas être utilisé...Complexit
´e - p.4/25
Temps d'exécution (1)
Le temps d'exécution d'un programme dépend : 1. du nombre de données, 2. de la taille du code, 3. du type d'ordinateur utilisé (processeur,mémoire),4. de la complexité en temps de l'algorithme "abstrait» sous-jacent.
Complexit
´e - p.5/25
Temps d'exécution (2)
Soitnla taille des données du problème etT(n)le temps d'exécution de l'algorithme. On distingue :Le temps du plus mauvais casTmax(n)
Correspond au temps maximum pris par l'algorithme pour un problème de taillen. Le temps moyenTmoy:Temps moyen d'exécution sur des données de taillen(?suppositions sur la distribution des données). T moy(n) =r? i=1p iTsi(n)piprobabilité que l'instructionsisoit exécutée,Tsi(n): temps requis pour l'exécution desi.
Complexit
´e - p.6/25
Temps d'exécution
Règles générales :
1. le temps d'exécution (t.e.) d'une affectation ou d'un test est considéré
comme constantc,2. Le temps d'une séquence d'instructions est la somme dest.e.des
instructions qui la composent,3. le temps d'un branchement conditionnel est égal au t.e. du test plus le max
des deux t.e. correspondant aux deux alternatives (dans le cas d'un temps max).4. Le temps d'une boucle est égal à la somme du coût du test + du corps de la
boucle + test de sortie de boucle.Complexit
´e - p.7/25
Problèmes du temps d'exécution (1)
Soit l'algorithme suivant :
Nom:Calcul d'une somme de carrés
Role:Calculer la valeur moyenne d'un tableau
Entrée:n : entier
Sortie:somme : réel
Déclaration:i: Naturel
début somme←0.0 pouri←0àn-1faire somme←somme+i*i finpour finComplexit
´e - p.8/25
Problèmes du temps d'exécution (2)
T moy(n) =Tmax(n) =c1+c1+n(c2+c3+c4+c5+c1) = 2c1+n??5i=1ci? avecc1: affectation,c2: incrémentation,c3test,c4addition,c5multiplication. Trop précis?1. Faux,2. Inutilisable.Notion de complexité : comportement asymptotique du t.e.:Tmax(n) =Tmoy(n)≈nC
Complexit´e - p.9/25
Estimation asymptotique
Définition 1Une fonction f est de l'ordre de g , écrit avec la notation Grand-O , pour toutn≥n0 selon la définition ci-dessus, on aura: f1(n) = 2n+ 3 =O(n3),2n+ 3 =O(n2),2n+ 3 =O(n)au plus juste
f2(n) = 7n2=O(2n),7n2=O(n2)au plus juste
mais,7n2N'EST PASO(n)Complexit
´e - p.10/25
Égalité de complexité
Définition 22 fonctions f et g sont d'égale complexité, ce qui s'écrit comme:O( f )= O( g ) (ouf=θ(g)), ssi
f =O(g)et g =O(f) exemples:n,2n, et0,1nsont d'égale complexité:O(n)=O(2n)=O(0,1n)O(n2)etO(0,1n2+n)sont d'égale complexité:O(n2)=O(0,1n2+n)par contre:2netn3se sont PAS d'égale complexité:O(2n)?=O(n3)
Définition 3une fonction f est de de plus petite complexité que g, ce qui s'écrit comme:O(f)2nest de plus petite complexité quen:O(log2n) =O(10n2) Complexit
´e - p.11/25
Propriétés
Réflexivité:
g=O(g)Transitivité : sif=O(g)etg=O(h)alorsf=O(h)Produit par un scalaire :O(λf) =O(f),λ >0.Somme et produit de fonctions :
O(f)+O(g)=O(max{f,g})O(f).O(g)=O(f.g)
Complexit
´e - p.12/25
Complexité d'une boucle
pouri←1ànfaire s finpour avec s=O(1). Temps de calcul des:Ts=CNombre d'appels des: nTemps de calcul total :T(n) =nTs=O(n)Complexité :O(n)
Complexit
´e - p.13/25
Boucles imbriquées
Théorème 1La complexité depboucles imbriquées de 1 ànne contenant que des instructions élémentaires est en O(np) Preuve:
vrai pourp= 1,supposons la ppt vrai à l'ordrep. Soit : pouri←1ànfaire instruction finpour Complexit´e - p.14/25
Boucles tant que
h←1 h←2*h fintantque Test, multiplication, affectation :O(1):T=CNombre d'itérations :log2(n).Temps de calcul :T(n) =Clog2(n) =O(log2(n))
Complexit
´e - p.15/25
Complexité d'un algorithme récursif (1)
Soit l'algorithme :
fonctionfactorielle(n: Naturel) :Naturel début sin = 0alors retourner1 sinon retournern*factorielle(n-1) finsi fin Complexit
´e - p.16/25
Complexité d'un algorithme récursif (2)
c 1test,c2multiplication.
T(0)=c1T(n)=c1+c2+T(n-1)
?T(n) =nc2+ (n+ 1)c1 SoitC= 2max{c1,c2}
Complexité enO(n).
Les calculs de complexité d'algorithmes récursifs induisent naturellement des suites. Complexit
´e - p.17/25
Algorithmes récursifs enO(log2(n))(1)
Théorème 2Soient,debut,finetn=fin-debuttrois entiers. La complexité de l'algorithme ci dessous est enO(log2(n)). procéduref(debut,fin) Déclaration Entiermilieu
début milieu←debut+fin 2sifin-milieu>1 et milieu-debut>1alors
s sinon sitestalors f (debut,milieu) sinon f (milieu,fin) finsi finsi fin Complexit´e - p.18/25
Algorithmes récursifs enO(log2(n))(2)
Tests, s :O(1)
T(n) =T(n
2) +C T(n 2) =T(n
4) +C...=...
T(1) =T(0) +C
T(n) =T(0) +Clog2(n)
Complexit´e - p.19/25
Algorithmes récursifs enO(nlog2(n))(1)
procéduref(debut,fin) Déclaration Entiermilieu
début milieu←debut+fin 2sifin-milieu>1 et milieu-debut>1alors
s 1sinon
pouri←1ànfaire s 2finpourf(début,milieu)f(milieu,fin)
finsi fin Complexit
´e - p.20/25
Algorithmes récursifs enO(nlog2(n))(2)
Tests, s :O(1)Boucle :O(n).
T(n) =n+ 2T(n
2) 2T(n 2) n+ 4T(n 4)...=...
2 p-1T(2) =n+ 2pT(1) T(n) =n?p+ 2p?T(1)
avecp= [log2(n)] On a de plus:O(nlog2(n) +nT(1)) =O(nlog2(n))
Complexit´e - p.21/25
Principales complexités
O(1): temps constant,O(log(n)): complexité logarithmique (Classe L), O(n): complexité linaire
(Classe P), O(nlog(n))O(n2),O(n3),O(np): quadratique, cubique,polynomiale (Classe P), O(pn)complexité exponentielle
(Classe EXPTIME)".
O(n!)complexité factorielle.
Complexit
´e - p.22/25
Influence de la complexité
n→2n. O(1) O(log2(n))
O(n) O(nlog2(n))
O(n2) O(n3) O(2n) t t+ 1 2t 2t+ 2n
4t 8t t2 1 log2(n) n nlog2(n) n2 n3 2n n= 102 1μs
6μs
0.1ms 0.6ms 10ms 1s 4×1016a
n= 103 1μs
10μs
1ms 10ms 1s 16.6min
n= 104 1μs
13μs
10ms 0.1s 100s
11,5j n= 105 1μs
17μs
0.1s 1.6s 2.7h 32a
n= 106 1μs
20μs
1s 19.9s 11,5j 32×103a
∞Complexit´e - p.23/25 Limites de la complexité
La complexité est un résultat asymptotique : un algorithme enO(Cn2)peut être plus efficace qu'un algorithme enO(C?n)pour de petites valeurs den siC?C?,Les traitements ne sont pas toujours linéaires?Il ne faut pas supposer d'ordres de grandeur entre les différentes constantes. Complexit
´e - p.24/25
Conseils
Qualités d'un algorithme :
1. Maintenable (facile à comprendre, coder, déboguer),
2. Rapide
Conseils :
1. Privilégier le point 2 sur le point 1 uniquement si on gagne en complexité.
2. "ce que fait» l'algorithme doit se lire lors d'une lecture rapide : Une idée
par ligne. Indenter le programme. 3. Faire également attention à la précision, la stabilité et la sécurité.
La rapidité d'un algorithme est un élément d'un tout définissant les qualités de celui-ci. Complexit
´e - p.25/25
quotesdbs_dbs28.pdfusesText_34
Complexit
´e - p.11/25
Propriétés
Réflexivité:
g=O(g)Transitivité :sif=O(g)etg=O(h)alorsf=O(h)Produit par un scalaire :O(λf) =O(f),λ >0.Somme et produit de fonctions :
O(f)+O(g)=O(max{f,g})O(f).O(g)=O(f.g)
Complexit
´e - p.12/25
Complexité d'une boucle
pouri←1ànfaire s finpour avec s=O(1).Temps de calcul des:Ts=CNombre d'appels des: nTemps de calcul total :T(n) =nTs=O(n)Complexité :O(n)
Complexit
´e - p.13/25
Boucles imbriquées
Théorème 1La complexité depboucles imbriquées de 1 ànne contenant que des instructions élémentaires est en O(np)Preuve:
vrai pourp= 1,supposons la ppt vrai à l'ordrep. Soit : pouri←1ànfaire instruction finpourComplexit´e - p.14/25
Boucles tant que
h←1 h←2*h fintantqueTest, multiplication, affectation :O(1):T=CNombre d'itérations :log2(n).Temps de calcul :T(n) =Clog2(n) =O(log2(n))
Complexit
´e - p.15/25
Complexité d'un algorithme récursif (1)
Soit l'algorithme :
fonctionfactorielle(n: Naturel) :Naturel début sin = 0alors retourner1 sinon retournern*factorielle(n-1) finsi finComplexit
´e - p.16/25
Complexité d'un algorithme récursif (2)
c1test,c2multiplication.
T(0)=c1T(n)=c1+c2+T(n-1)
?T(n) =nc2+ (n+ 1)c1SoitC= 2max{c1,c2}
Complexité enO(n).
Les calculs de complexité d'algorithmes récursifs induisent naturellement des suites.Complexit
´e - p.17/25
Algorithmes récursifs enO(log2(n))(1)
Théorème 2Soient,debut,finetn=fin-debuttrois entiers. La complexité de l'algorithme ci dessous est enO(log2(n)). procéduref(debut,fin)Déclaration Entiermilieu
début milieu←debut+fin2sifin-milieu>1 et milieu-debut>1alors
s sinon sitestalors f (debut,milieu) sinon f (milieu,fin) finsi finsi finComplexit´e - p.18/25
Algorithmes récursifs enO(log2(n))(2)
Tests, s :O(1)
T(n) =T(n
2) +C T(n2) =T(n
4) +C...=...
T(1) =T(0) +C
T(n) =T(0) +Clog2(n)
Complexit´e - p.19/25
Algorithmes récursifs enO(nlog2(n))(1)
procéduref(debut,fin)Déclaration Entiermilieu
début milieu←debut+fin2sifin-milieu>1 et milieu-debut>1alors
s1sinon
pouri←1ànfaire s2finpourf(début,milieu)f(milieu,fin)
finsi finComplexit
´e - p.20/25
Algorithmes récursifs enO(nlog2(n))(2)
Tests, s :O(1)Boucle :O(n).
T(n) =n+ 2T(n
2) 2T(n 2) n+ 4T(n4)...=...
2 p-1T(2) =n+ 2pT(1)T(n) =n?p+ 2p?T(1)
avecp= [log2(n)]On a de plus:O(nlog2(n) +nT(1)) =O(nlog2(n))
Complexit´e - p.21/25
Principales complexités
O(1): temps constant,O(log(n)): complexité logarithmique (Classe L),O(n): complexité linaire
(Classe P), O(nlog(n))O(n2),O(n3),O(np): quadratique, cubique,polynomiale (Classe P),O(pn)complexité exponentielle
(ClasseEXPTIME)".
O(n!)complexité factorielle.
Complexit
´e - p.22/25
Influence de la complexité
n→2n. O(1)O(log2(n))
O(n)O(nlog2(n))
O(n2) O(n3) O(2n) t t+ 1 2t2t+ 2n
4t 8t t2 1 log2(n) n nlog2(n) n2 n3 2n n= 1021μs
6μs
0.1ms 0.6ms 10ms 1s4×1016a
n= 1031μs
10μs
1ms 10ms 1s16.6min
n= 1041μs
13μs
10ms 0.1s 100s11,5j n= 105
1μs
17μs
0.1s 1.6s 2.7h 32an= 106
1μs
20μs
1s 19.9s 11,5j32×103a
∞Complexit´e - p.23/25Limites de la complexité
La complexité est un résultat asymptotique : un algorithme enO(Cn2)peut être plus efficace qu'un algorithme enO(C?n)pour de petites valeurs den siC?C?,Les traitements ne sont pas toujours linéaires?Il ne faut pas supposer d'ordres de grandeur entre les différentes constantes.Complexit
´e - p.24/25
Conseils
Qualités d'un algorithme :
1. Maintenable (facile à comprendre, coder, déboguer),
2. Rapide
Conseils :
1. Privilégier le point 2 sur le point 1 uniquement si on gagne en complexité.
2. "ce que fait» l'algorithme doit se lire lors d'une lecture rapide : Une idée
par ligne. Indenter le programme.3. Faire également attention à la précision, la stabilité et la sécurité.
La rapidité d'un algorithme est un élément d'un tout définissant les qualités de celui-ci.Complexit
´e - p.25/25
quotesdbs_dbs28.pdfusesText_34[PDF] masse et quantité de matière exercice
[PDF] l'alcool utilisé comme antiseptique local peut être
[PDF] production primaire nette
[PDF] productivité nette de l'écosystème
[PDF] production primaire et secondaire
[PDF] productivité nette de l écosystème
[PDF] taux d'évolution calcul
[PDF] taux d'endettement entreprise
[PDF] numero ine sur internet
[PDF] inscription lycée hors secteur
[PDF] nombre de mole formule
[PDF] nombre de mole d'un gaz
[PDF] nombre d'oxydation exercices corrigés
[PDF] exercices priorités opératoires 5ème pdf