Scribd
Importer
0 vues2 pages

Activity 1

Le document présente des exercices sur l'analyse de complexité, incluant la complexité d'une boucle while et la fonction f(n) avec une complexité totale de O(n log n). Il décrit également l'algorithme de Dijkstra pour trouver la distance minimale entre des sommets, avec un exemple illustrant les étapes de traitement des sommets. Enfin, il aborde la complexité asymptotique de deux fonctions, f1(n) avec une complexité de O(n²) et f2(n) avec une complexité de O(log n).

Transféré par

adelb0622
Copyright
© All Rights Reserved
Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.
Formats disponibles
Téléchargez aux formats PDF, TXT ou lisez en ligne sur Scribd
0 vues2 pages

Activity 1

Le document présente des exercices sur l'analyse de complexité, incluant la complexité d'une boucle while et la fonction f(n) avec une complexité totale de O(n log n). Il décrit également l'algorithme de Dijkstra pour trouver la distance minimale entre des sommets, avec un exemple illustrant les étapes de traitement des sommets. Enfin, il aborde la complexité asymptotique de deux fonctions, f1(n) avec une complexité de O(n²) et f2(n) avec une complexité de O(log n).

Transféré par

adelb0622
Copyright
© All Rights Reserved
Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.
Formats disponibles
Téléchargez aux formats PDF, TXT ou lisez en ligne sur Scribd

Activité 1- Exercice Chapitre 1

Exercice 1- Analyse de complexité


1. Complexité de la boucle while : 𝑂(log 2 𝑛 )
2. Complexité totale de la fonction f(n) : 𝑂(𝑛 𝑙𝑜𝑔2 𝑛)
3. Justification :
 La variable 𝑗 commence à 1 et est multipliée par 2 à chaque itération.
 La boucle s'arrête lorsque 𝑗 ≥ 𝑛
 Si 𝑘 est le nombre d'itérations, alors 𝑗 prendra les valeurs d’une suite
géométrique à base 2 : 1, 2, 4, 8, … , 2𝑘
 La condition d'arrêt est 2𝑘 ≥ 𝑛.
 Pour trouver 𝑘, on prend le logarithme de base 2 : 𝑘 ≥ log 2 𝑛
 Boucle externe (for i in range(n)) s'exécute 𝑛 fois (pour i = 0 à n-1).
 À chaque exécution de la boucle externe, la boucle interne s'exécute avec une
complexité de 𝑂(𝑙𝑜𝑔 𝑛)
 Complexité totale de la fonction f(n): 𝑂(𝑛 𝑙𝑜𝑔 𝑛)

Exercice 2- Algorithme de Dijkstra


Initialisation

Les distances de tous les sommets à l'infini (∞), sauf pour le sommet de départ A, qui
est à 0.

Sommet Distance 𝑑 Prédécesseur 𝑝 Visité


A 0 - Non
B ∞ - Non
C ∞ - Non
D ∞ - Non

Étape 1 : Traitement du sommet A

Sommet Distance 𝑑 Prédécesseur 𝑝 Visité


𝐴 0 − Oui
𝐵 3 𝐴 Non
𝐶 6 𝐴 Non
𝐷 ∞ − Non

Étape 2 : Traitement du sommet B

Sommet Distance 𝑑 Prédécesseur 𝑝 Visité


𝐴 0 − Oui
𝐵 3 𝐴 Oui
𝐶 6 𝐴 Non
𝐷 7 𝐵 Non

1|Page
Étape 3 : Traitement du sommet C

Sommet Distance 𝑑 Prédécesseur 𝑝 Visité


𝐴 0 − Oui
𝐵 3 𝐴 Oui
𝐶 6 𝐴 Non
𝐷 7 𝐵 𝑜𝑢 𝐶 Non

Conclusion :

La distance minimale entre A et D est 7.

Exercice 3- Complexité Asymptotique

Fonction 1 : f1(n)

Complexité temporelle : 𝑂(𝑛2 )


 Boucle externe (for i in range(n)): Cette boucle s'exécute n fois (pour i
= 0 à n-1)
 Boucle interne (for j in range(i, n)): Le nombre d'itérations de cette
boucle est :
𝐶(𝑛) = 𝑛 + (𝑛 − 1) + (𝑛 − 2) + … + 1
𝑛(𝑛 + 1) 1 2 1
𝐶 (𝑛 ) = = 𝑛 + 𝑛
2 2 2
En notation Big-O, on ne retient que le terme de plus haut degré et on ignore les
coefficients. Donc le terme dominant est 𝑛2 .

Fonction 2 : f2(n)

Complexité temporelle : 𝑂(log 𝑛)

 L'algorithme se compose de deux parties séquentielles : une boucle while et


une boucle for. La complexité totale est déterminée par la partie la plus lente
(celle avec la plus grande complexité).
 Boucle while:
o La variable 𝑖 commence à 1 et est multipliée par 2 à chaque itération
o La boucle s'arrête lorsque 𝑖 ≥ 𝑛
o Si 𝑘 est le nombre d'itérations, on a 2𝑘 ≈ 𝑛, soit 𝑘 ≈ 𝑙𝑜𝑔2 (𝑛)
o La complexité de cette partie est 𝑂(log 𝑛)

 Boucle for:
o for k in range(10): Cette boucle s'exécute exactement 10 fois, quel
que soit la valeur de 𝑛
o La complexité de cette partie est 𝑂(1) (complexité constante)

La complexité totale est la somme des complexités : 𝑂(𝑙𝑜𝑔 𝑛) + 𝑂(1). Dans l'analyse
asymptotique, la partie dominante est log 𝑛.

2|Page

Vous aimerez peut-être aussi