[PDF] [PDF] Calculs de complexité dalgorithmes

[PDF] TD : Complexité des algorithmes

Conclure en donnant la complexité temporelle pour chaque algorithme PROPOSITION DE CORRIGE Exercice 2 Revoir poly, transparents 33, 34, et 35

[PDF] SUJET + CORRIGE

Dans cet exercice, nous allons adapter des algorithmes de tri vus en cours Rappel : La complexité, vue en cours, de troisPartitionner(T,g,d) est Θ(d − g + 1)

[PDF] Informatique - TD No 7 Calcul de complexité

9 fév 2004 · Exercice 1 Écrire l'algorithme qui recherche un élément dans un Corrige 1 on compte le nombre de comparaison avec les éléments de 

[PDF] Complexité Corrigé - Fabrice Rossi

12 mar 2012 · Comme la boucle s'exécute n fois, le temps d'exécution du programme est alors en Θ(n) 2 Correction de l'exercice 1 2 Le programme étudié est 

[PDF] Algorithmique I - École normale supérieure de Lyon

Ce polycopié rassemble les cours et travaux dirigés (avec corrigés) du and analysis of algorithms, contient les notes de cours et exercices (certains corrigés) d'un Notons enfin qu'il existe des algorithmes de complexité meilleure que celle 

[PDF] Exercice corrigé Complexité en moyenne du MergeSort et - Ensiwiki

On rappelle que les complexités en pire cas de l'algorithme de tri-fusion ( MergeSort, J von Neumann 1945) et de l'algorithme de tri rapide ( QuickSort, C A R  

[PDF] Travaux Dirigés Algorithmique no3

4 Montrer que la complexité de cet algorithme est Θ(n) Peut-on faire mieux ? Exercice 5 (Calcul du maximum d' 

[PDF] Calculs de complexité dalgorithmes

○Complexité des algorithmes ○Exemples de calcul de complexité Exercice ○Utilisez la méthode du polynôme caractéristique pour résoudre l'équation de

[PDF] corrigé - IRIF

17 nov 2009 · Exercice 1 – Récurrence Expliquez l'algorithme de cours pour ce problème 2 On a la récurrence suivante sur la complexité de cet algo :

[PDF] preuve d'algorithme

[PDF] comment calculer complexité algorithmique

[PDF] exemples de démarches et de raisonnements prouvant la terminaison et la correction d un algorithme

[PDF] complexité boucle for

[PDF] complexité algorithmique cours

[PDF] système de congruence exercice

[PDF] résoudre équation congruence

[PDF] exercice congruence

[PDF] théorème chinois pdf

[PDF] resoudre systeme congruence

[PDF] calcul consommation ampoule 100w

[PDF] consommation ampoule 60w

[PDF] combien coute une ampoule allumée

[PDF] calcul consommation ampoule led

[PDF] lumiere allumée toute la nuit consommation

1

Calculs de complexité

d'algorithmes

Notations asymptotiques : 0 et

Complexité

des algorithmes

Exemples de calcul de complexité

2

Complexités d'un algorithme

Un algorithme à

partir d'une donnée établit un résultat . La taille de la donnée est mesurée par un entier n. complexité temporelle une fonction de n qui mesure le temps de calcul pour une donnée de taille n complexité en mémoire

une fonction de n qui mesure la place mémoire utilisée pour le calcul sur une donnée de taille n

3

Complexités temporelles

Dans le pire des cas : donne une borne supérieure sur le temps de calcul pour toutes les données de taille n

En moyenne : fait la moyenne des temps de calculs pour toutes les données de taille n 4

Mesure-t-on vraiment le temps de calcul ?

Non, car le temps de calcul dépend de la machine

On évalue le nombre d'opérations "élémentaires" faites (additions, multiplications, etc.)

On obtient donc une estimation du temps de calcul àune constante multiplicative près (le temps mis par la machine pour faire une opération "élémentaire")

Dans cette estimation, on ne considère que le

terme dominant 5

Définitions

On dit que f est

dominée par g (noté f = O (g)) lorsque

On dit que f est

du même ordre de grandeur que g et l'on note f = (g) lorsque f=O(g) et g=O(f). 0 0 0 n cg n f n n c n 6

Définitions

f est négligeable devant g, (noté f =o(g)) lorsque f(n)/g(n) tend vers 0 quand n tend vers l'infini

On dit que f est

équivalente

g lorsque f(n)/g(n) tend vers 1 lorsque n tend vers l'infini 7

Relations entre O, o et autres

f est négligeable devant g implique f est dominée par g ? f est

équivalente

àg impliquef est du même ordre de grandeur que g ? 8

Remarque

Hormis pour l'équivalence, ces notions sont indépendantes des constantes multiplicatives non nulles.Par exemple : si

f est négligeable devant g, alors c f est négligeable devant c'g pour tout réels c et c' non nuls. 9

Polynômes et notations O et

Soit P(n) un polynôme en n. Pour quelles valeurs de p a-t-on P(n)=O(n p

Pour quelles valeurs de p a-t-on P(n)=

(n p 10

Montrer que pour tout entier k, on a

1 0 n kk i in 11

Échelle De Comparaison

Exercice

Soient les fonctions

f 1 (n)=n, f 2 (n)=2 n f 3 (n)=n 2 , f 4 (n)=2n, f 5 (n)=n n , f 6 (n)=log n, f 7 (n)=n!, f 8 (n)= nlog n

Pour chaque couple (i, j) dire si on a

f i =o(f j f i =O(f j f i (f j 12 10 9

Instructions/secondes

(1 gigaHertz) n 5 10 15 20 100
1 000 lo g n 3 1 0 -9 s4 1 0 -9 s4 1 0 -9 s5 1 0 -9 s7 1 0 -9 s1 0 -8 s 2n 10 10 -9 s2 1 0 -8 s3 1 0 -8 s4 1 0 -8 s2 1 0 -7 s2 1 0 -6 s nlog n 1 2 10 -9 s3 1 0 -8 s6 1 0 -8 s1 0 -7 s7 1 0 -7 s1 0 -5 s n 2 25 10
-9 s1 0 -7 s2 2 5 1 0 -7 s4 1 0 -7 s1 0 -5 s1 0 -3 s n 5 3 10 -6 s1 0 -4 s7 5 9 1 0 -4 s3 1 0 -3 s1 0 s 1 0 6 s 11 j o urs 2 n 32 10
-9 s1 0 -6 s3 2 8 1 0 -5 s1 0 -3quotesdbs_dbs28.pdfusesText_34