TD_1

TD : Complexité en Temps

Exercice 1 : Analyse de la complexité d'un algorithme simple

Enoncé :
On te donne l'algorithme suivant :

1. Quel est l'objectif de cet algorithme ?

2. Quelle est la complexité en temps de cet algorithme ?

Solution :

1. Objectif de l'algorithme : Cet algorithme calcule la somme des entiers de 1 à n.

Par exemple, si n = 4, il renverra 1 + 2 + 3 + 4 = 10.
2. Analyse de la complexité en temps :

L'algorithme comporte une seule boucle for qui exécute l'instruction s += i n

fois (car i va de 1 à n). Cela signifie qu'il y a n opérations de sommation.

La complexité en temps de cet algorithme est donc linéaire, notée O(n).

Exercice 2 : Analyse d'un algorithme avec une boucle imbriquée

Enoncé :
On te donne l'algorithme suivant :
 1. Quel est l'objectif de cet algorithme ?
2. Quelle est la complexité en temps de cet algorithme ?

Solution :

1. Objectif de l'algorithme : Cet algorithme calcule le produit de i * j pour tous

les couples (i, j) où i et j vont de 1 à n. En d'autres termes, il multiplie toutes
les valeurs possibles de i et j entre 1 et n.
2. Analyse de la complexité en temps :
o La première boucle for (sur i) s'exécute n fois.
o La deuxième boucle for (sur j) s'exécute également n fois pour chaque
valeur de i.

Cela donne un total de n * n = n² itérations, donc la complexité en temps est

O(n²).

Exercice 3 : Complexité d'un algorithme avec une condition

Enoncé :
On te donne l'algorithme suivant :

1. Quel est l'objectif de cet algorithme ?

2. Quelle est la complexité en temps de cet algorithme ?

Solution :

1. Objectif de l'algorithme : Cet algorithme recherche un élément x dans un

tableau arr. Il retourne True si l'élément x est trouvé, sinon il retourne False.
2. Analyse de la complexité en temps :

L'algorithme parcourt tous les éléments du tableau arr pour trouver x. La boucle
for s'exécute une fois pour chaque élément du tableau. Si la taille du tableau est
n, alors la boucle s'exécute n fois dans le pire des cas.

La complexité en temps est donc O(n).

Exercice 4 : Complexité d'un algorithme avec une réduction du problème

Enoncé :
On te donne l'algorithme suivant, qui calcule la somme des éléments d'une liste en
utilisant la technique de "diviser pour régner" :

1. Quel est l'objectif de cet algorithme ?

2. Quelle est la complexité en temps de cet algorithme ?

Solution :

1. Objectif de l'algorithme : Cet algorithme calcule la somme des éléments d'un

tableau arr en divisant récursivement le tableau en deux sous-tableaux et en les
additionnant ensuite. Il est basé sur la technique de "diviser pour régner".
2. Analyse de la complexité en temps :
o Dans chaque appel récursif, le tableau est divisé en deux parties égales.
o Pour chaque niveau de récursion, on effectue une addition des deux sous-
tableaux.
o Le nombre de niveaux de récursion est logarithmique, soit O(log n), car à
chaque niveau le problème est divisé en deux.
o À chaque niveau, nous devons parcourir tous les éléments du tableau
pour les additionner, ce qui prend O(n) opérations au total.

La complexité en temps de cet algorithme est donc O(n), même si la récursion

divise le tableau en deux à chaque appel.

Exercice 5 : Complexité d'un algorithme avec deux boucles imbriquées

Enoncé :
On te donne l'algorithme suivant qui calcule le produit scalaire de deux vecteurs :
 1. Quel est l'objectif de cet algorithme ?
2. Quelle est la complexité en temps de cet algorithme ?

Solution :

1. Objectif de l'algorithme : Cet algorithme calcule le produit scalaire de deux

vecteurs v1 et v2. Cependant, au lieu de simplement multiplier les éléments
correspondants et les additionner, il calcule le produit pour chaque combinaison
possible des éléments de v1 et v2.
2. Analyse de la complexité en temps :
o La première boucle for s'exécute n fois.
o La deuxième boucle for s'exécute également n fois pour chaque itération
de la première boucle.

Cela donne un total de n * n = n² opérations, ce qui signifie que la complexité

en temps est O(n²).

Conclusion

Dans tous ces exercices, la complexité en temps des algorithmes a été déterminée en
fonction du nombre d'itérations des boucles et de la manière dont l'algorithme divise ou
traite les données. Voici un récapitulatif des complexes de chaque exercice :

1. O(n)
2. O(n²)
3. O(n)
4. O(n)
5. O(n²)

Chaque analyse est basée sur la façon dont les boucles et récursions interagissent avec la
taille des entrées. Pour bien comprendre la complexité, il faut se concentrer sur le
nombre d'opérations effectuées en fonction de l'entrée.
Exercice 6 : Recherche d'un élément dans une liste triée (Binary Search)

Enoncé :
On te donne l'algorithme suivant qui effectue une recherche binaire dans un tableau trié
arr pour trouver un élément x.

1. Quel est l'objectif de cet algorithme ?

2. Quelle est la complexité en temps de cet algorithme ?

Solution :

1. Objectif de l'algorithme : L'algorithme effectue une recherche binaire pour

trouver un élément x dans un tableau trié arr. Il divise successivement le tableau
en deux moitiés pour réduire l'espace de recherche à chaque itération.
2. Analyse de la complexité en temps :
o À chaque itération, le tableau est divisé en deux sous-tableaux. Cela
réduit de moitié le nombre d'éléments à vérifier.
o Le nombre de divisions nécessaires pour réduire le tableau à une taille de
1 est logarithmique par rapport à la taille du tableau.
o Donc, la complexité en temps est O(log n), où n est la taille du tableau.

Exercice 7 : Calcul de la factorielle avec récursion

Enoncé :
On te donne l'algorithme suivant qui calcule la factorielle de n de manière récursive.
 1. Quel est l'objectif de cet algorithme ?
2. Quelle est la complexité en temps de cet algorithme ?

Solution :

1. Objectif de l'algorithme : Cet algorithme calcule la factorielle de n, c'est-à-dire

le produit de tous les entiers de 1 à n. Par exemple, factorielle(4) renvoie 4 * 3 *
2 * 1 = 24.
2. Analyse de la complexité en temps :
o L'algorithme utilise la récursion pour calculer la factorielle. À chaque
appel récursif, il calcule n * factorielle(n - 1), ce qui crée une nouvelle
branche de récursion jusqu'à ce que n atteigne 0.
o Le nombre d'appels récursifs est égal à n, donc le nombre total
d'opérations effectuées est directement proportionnel à n.
o La complexité en temps est donc O(n).

Exercice 8 : Tri par insertion

Enoncé :
On te donne l'algorithme suivant pour trier un tableau arr en utilisant le tri par insertion.

1. Quel est l'objectif de cet algorithme ?

2. Quelle est la complexité en temps de cet algorithme dans le pire des cas ?

Solution :

1. Objectif de l'algorithme : Le tri par insertion trie un tableau en insérant chaque

élément à sa position correcte dans une sous-liste triée. À chaque itération,
l'élément à l'index i est comparé aux éléments précédents et inséré à sa place
correcte.
2. Analyse de la complexité en temps :
o La boucle externe s'exécute n - 1 fois.
o La boucle interne compare l'élément courant avec tous les éléments
précédents jusqu'à ce qu'il trouve la bonne position. Dans le pire des cas
(quand les éléments sont dans l'ordre inverse), la boucle interne s'exécute
i fois pour chaque valeur de i.
o La somme des itérations de la boucle interne est donc 1 + 2 + ... + (n - 1),
soit une somme arithmétique égale à n(n - 1) / 2, soit O(n²).
La complexité en temps du tri par insertion dans le pire des cas est donc O(n²).

Exercice 9 : Tri à bulles (Bubble Sort)

Enoncé :
On te donne l'algorithme suivant pour trier un tableau arr en utilisant le tri à bulles.

1. Quel est l'objectif de cet algorithme ?

2. Quelle est la complexité en temps de cet algorithme dans le pire des cas ?

Solution :

1. Objectif de l'algorithme : Le tri à bulles trie un tableau en comparant chaque

paire d'éléments voisins et en les échangeant si nécessaire. Cela "fait monter"
l'élément le plus grand à la fin du tableau après chaque itération de la boucle
externe.
2. Analyse de la complexité en temps :
o La boucle externe s'exécute n fois.
o La boucle interne compare et échange des éléments voisins n - i - 1 fois
pour chaque itération de la boucle externe.
o Dans le pire des cas, il faut effectuer un échange à chaque comparaison,
ce qui donne un total de n * (n - 1) / 2 comparaisons et échanges, soit
O(n²).

La complexité en temps du tri à bulles dans le pire des cas est donc O(n²).

Exercice 10 : Recherche linéaire avec retour anticipé

Enoncé :
On te donne l'algorithme suivant qui recherche un élément x dans une liste arr. Si x est
trouvé, il retourne l'indice de x, sinon il retourne -1.
 1. Quel est l'objectif de cet algorithme ?
2. Quelle est la complexité en temps de cet algorithme dans le pire des cas ?

Solution :

1. Objectif de l'algorithme : L'algorithme effectue une recherche linéaire dans la

liste arr. Si l'élément x est trouvé, il renvoie l'indice de cet élément, sinon il
renvoie -1.
2. Analyse de la complexité en temps :
o L'algorithme parcourt la liste entière au maximum pour trouver l'élément.
Dans le pire des cas, cela signifie qu'il doit examiner tous les éléments du
tableau.
o Si la taille du tableau est n, le nombre d'opérations dans le pire des cas est
n.
o La complexité en temps est donc O(n).

Conclusion

Voici un récapitulatif des complexités en temps des nouveaux exercices :

6. O(log n) (Recherche binaire)

7. O(n) (Calcul de la factorielle)
8. O(n²) (Tri par insertion)
9. O(n²) (Tri à bulles)
10. O(n) (Recherche linéaire)

Ces exercices couvrent divers types d'algorithmes classiques, y compris ceux de

recherche, de tri et de récursion, et montrent l'importance d'analyser la façon dont la
taille de l'entrée affecte la performance de l'algorithme.
Exercice 1 : Recherche binaire

Enoncé :
On te donne l'algorithme suivant qui effectue une recherche binaire dans un tableau trié
arr pour trouver un élément x :

1. Quel est l'objectif de cet algorithme ?

2. Quelle est la complexité en temps de cet algorithme ?

Solution :

1. Objectif de l'algorithme :
Cet algorithme effectue une recherche binaire dans un tableau trié arr. La
recherche binaire consiste à diviser l'espace de recherche en deux moitiés à
chaque itération, ce qui réduit de moitié le nombre d'éléments à examiner.
2. Analyse de la complexité en temps :
o À chaque itération de la boucle while, le tableau est divisé en deux parties
égales.
o Le nombre d'itérations nécessaires pour réduire l'espace de recherche à
une seule valeur est proportionnel à log₂(n), où n est la taille du tableau.
o La complexité en temps de cet algorithme est donc O(log n), car à chaque
itération la taille de l'espace de recherche est réduite de moitié.

Exercice 2 : Diviser pour régner (Exemple de la multiplication de deux grands

nombres)

Enoncé :
On te donne un algorithme pour multiplier deux grands nombres en utilisant une
méthode de type "diviser pour régner", qui divise les nombres en deux parties égales et
les multiplie récursivement.
 1. Quel est l'objectif de cet algorithme ?
2. Quelle est la complexité en temps de cet algorithme ?

Solution :

1. Objectif de l'algorithme :
Cet algorithme est une variante de la multiplication de Karatsuba, qui utilise la
méthode "diviser pour régner" pour multiplier deux nombres grands. Au lieu de
multiplier directement les grands nombres, l'algorithme divise les nombres en
deux parties égales et effectue des multiplications sur ces parties, puis combine
les résultats.
2. Analyse de la complexité en temps :
o L'algorithme divise chaque nombre en deux à chaque étape récursive.
o À chaque niveau de récursion, il y a trois multiplications à effectuer
(deux petites et une combinée).
o La taille des nombres est réduite de moitié à chaque niveau, et le nombre
d'étapes nécessaires pour diviser le nombre jusqu'à atteindre des cas de
base (où les nombres sont inférieurs à 10) est logarithmique par rapport à
la taille du nombre.
o La complexité en temps est donc O(log n) à chaque niveau de récursion,
mais il y a également une multiplication supplémentaire par une
constante dans chaque niveau, ce qui donne une complexité O(log n)
pour la multiplication de grands nombres, en termes de la taille des
nombres.

Exercice 3 : Arbre binaire de recherche

Enoncé :
On te donne l'algorithme suivant qui recherche un élément x dans un arbre binaire de
recherche :
 1. Quel est l'objectif de cet algorithme ?
2. Quelle est la complexité en temps de cet algorithme ?

Solution :

1. Objectif de l'algorithme :
Cet algorithme recherche un élément x dans un arbre binaire de recherche
(ABR). Dans un ABR, les valeurs à gauche d'un nœud sont plus petites que la
valeur du nœud, et les valeurs à droite sont plus grandes. L'algorithme compare
la valeur recherchée avec la valeur du nœud courant et décide d'explorer soit le
sous-arbre gauche, soit le sous-arbre droit en fonction de la comparaison.
2. Analyse de la complexité en temps :
o L'algorithme suit un chemin dans l'arbre à chaque étape, en fonction de la
comparaison entre la valeur du nœud et la valeur recherchée.
o Dans un arbre binaire équilibré, le nombre de niveaux de l'arbre est
logarithmique par rapport au nombre d'éléments, soit log₂(n).
o Ainsi, dans le pire des cas, l'algorithme devra traverser un chemin qui est
proportionnel à la hauteur de l'arbre, et donc la complexité en temps est
O(log n).

Exercice 4 : Trouver le plus grand commun diviseur (PGCD) avec l'algorithme

d'Euclide

Enoncé :
On te donne l'algorithme suivant pour calculer le PGCD de deux entiers a et b en
utilisant l'algorithme d'Euclide :

1. Quel est l'objectif de cet algorithme ?

2. Quelle est la complexité en temps de cet algorithme ?
Solution :

1. Objectif de l'algorithme :
L'algorithme calcule le PGCD (plus grand commun diviseur) de deux entiers a et
b. L'algorithme d'Euclide repose sur le principe que le PGCD de deux nombres a
et b est le même que celui de b et a % b.
2. Analyse de la complexité en temps :
o À chaque itération de la boucle, la taille de b diminue (car a % b est
toujours plus petit que b).
o La taille de b est divisée approximativement par 2 à chaque étape (dans le
cas de la division).
o Le nombre d'itérations nécessaires est proportionnel au logarithme de la
plus petite des deux valeurs a et b.
o La complexité en temps de cet algorithme est donc O(log n), où n est le
plus petit des deux nombres.

Exercice 5 : Recherche dans un tableau trié avec retour anticipé

Enoncé :
On te donne l'algorithme suivant qui effectue une recherche dans un tableau trié arr pour
trouver un élément x. L'algorithme utilise une approche similaire à la recherche binaire,
mais avec un retour anticipé.

1. Quel est l'objectif de cet algorithme ?

2. Quelle est la complexité en temps de cet algorithme ?

Solution :

1. Objectif de l'algorithme :
Cet algorithme effectue une recherche dans un tableau trié arr en utilisant une
méthode de recherche binaire pour trouver un élément x. Si l'élément est trouvé,
il renvoie son indice, sinon il renvoie -1.
2. Analyse de la complexité en temps :
 o L'algorithme divise le tableau en deux à chaque itération (comme dans la
recherche binaire).
o À chaque itération, il élimine la moitié de l'espace de recherche, ce qui
signifie qu'il réduit de moitié le nombre d'éléments à vérifier.
o Le nombre d'itérations nécessaires pour réduire l'espace de recherche à un
seul élément est proportionnel à log₂(n), où n est la taille du tableau.
o La complexité en temps est donc O(log n).

Conclusion

Voici un récapitulatif des complexités en temps des exercices :

1. O(log n) (Recherche binaire)

2. O(log n) (Multiplication de Karatsuba)
3. O(log n) (Recherche dans un arbre binaire de recherche)
4. O(log n) (Algorithme d'Euclide pour le PGCD)
5. O(log n) (Recherche optimisée dans un tableau trié)

Tous ces algorithmes bénéficient de la complexité logarithmique, ce qui signifie qu'ils

sont particulièrement efficaces lorsque la taille de l'entrée devient grande. La réduction
logarithmique de l'espace de recherche à chaque étape est ce qui permet d'obtenir cette
efficacité.
Exercice 1 : Implémentation du Tri Fusion

Enoncé :
On te donne l'algorithme suivant qui implémente le tri fusion pour trier un tableau arr :

1. Quel est l'objectif de cet algorithme ?

2. Quelle est la complexité en temps de cet algorithme ?

Solution :

1. Objectif de l'algorithme :
Cet algorithme effectue un tri fusion pour trier un tableau arr. Le tri fusion
repose sur le principe du diviser pour régner : le tableau est divisé en deux
sous-tableaux, chaque sous-tableau est trié récursivement, puis les sous-tableaux
triés sont fusionnés pour obtenir le tableau final trié.
2. Analyse de la complexité en temps :
o Division : À chaque étape, le tableau est divisé en deux, ce qui prend un
temps constant (la division de l'array ne prend pas beaucoup de temps,
car c'est une simple opération d'indexation).
o Fusion : À chaque niveau de récursion, deux sous-tableaux sont
fusionnés. L'algorithme de fusion parcourt chaque élément de ces sous-
tableaux une seule fois, ce qui prend O(n), où n est la taille du tableau.
o Récursion : L'algorithme divise le tableau jusqu'à ce qu'il atteigne des
sous-tableaux de taille 1. Le nombre de niveaux de récursion est log₂(n),
où n est la taille du tableau.
Ainsi, la complexité totale en temps est O(n log n), où n est la taille du tableau.

Exercice 2 : Complexité du Tri Fusion dans le pire des cas

Enoncé :
On te donne l'algorithme suivant pour le tri fusion. Quelle est la complexité en temps
dans le pire des cas ?

1. Quel est l'objectif de cet algorithme ?

2. Quelle est la complexité en temps dans le pire des cas ?

Solution :

1. Objectif de l'algorithme :
L'objectif de cet algorithme est de trier un tableau arr en utilisant le tri fusion. Le
tableau est divisé en sous-tableaux de plus en plus petits jusqu'à ce que chaque
sous-tableau ait une taille de 1. Ensuite, les sous-tableaux sont fusionnés de
manière ordonnée pour obtenir le tableau trié.
2. Analyse de la complexité en temps dans le pire des cas :
o À chaque niveau de récursion, le tableau est divisé en deux. Cela
continue jusqu'à ce que les sous-tableaux aient une taille de 1, ce qui
nécessite log₂(n) niveaux de récursion.
 o À chaque niveau de récursion, l'algorithme effectue une fusion de deux
sous-tableaux. L'opération de fusion est linéaire en fonction du nombre
d'éléments à fusionner, ce qui prend O(n) à chaque niveau de récursion.
o Comme il y a log₂(n) niveaux de récursion et que chaque fusion prend
O(n), la complexité totale en temps est O(n log n), même dans le pire des
cas.

Exercice 3 : Tracer les appels récursifs du Tri Fusion

Enoncé :
On te donne un tableau à trier arr = [38, 27, 43, 3, 9, 82, 10]. Trace les appels récursifs
effectués par le tri fusion, puis analyse la complexité de ces appels.

1. Tracer l'exécution du tri fusion sur ce tableau.

2. Quelle est la complexité en termes d'appels récursifs ?

Solution :

1. Exécution du tri fusion :

o Première division :
Tableau initial : [38, 27, 43, 3, 9, 82, 10]
Divisé en deux sous-tableaux : [38, 27, 43] et [3, 9, 82, 10]
o Division du premier sous-tableau [38, 27, 43] :
Divisé en [38] et [27, 43]
Le sous-tableau [38] est déjà trié.
Le sous-tableau [27, 43] est divisé en [27] et [43].
Fusion de [27] et [43] pour donner [27, 43].
Fusion de [38] et [27, 43] pour donner [27, 38, 43].
o Division du deuxième sous-tableau [3, 9, 82, 10] :
Divisé en [3, 9] et [82, 10]
Le sous-tableau [3, 9] est divisé en [3] et [9].
Fusion de [3] et [9] pour donner [3, 9].
Le sous-tableau [82, 10] est divisé en [82] et [10].
Fusion de [82] et [10] pour donner [10, 82].
Fusion de [3, 9] et [10, 82] pour donner [3, 9, 10, 82].
o Fusion finale :
Fusion de [27, 38, 43] et [3, 9, 10, 82] pour donner [3, 9, 10, 27, 38, 43,
82].
2. Complexité des appels récursifs :
o À chaque niveau de récursion, le tableau est divisé en deux sous-tableaux
égaux. Cela produit une profondeur de récursion de log₂(n) niveaux.
o À chaque niveau, tous les éléments du tableau doivent être comparés et
fusionnés, ce qui prend O(n) opérations par niveau de récursion.
o Le nombre total d'opérations est donc O(n log n) en termes d'appels
récursifs, où n est la taille du tableau.
Exercice 4 : Comparaison entre Tri Fusion et Tri à Bulles

Enoncé :
Compare les performances du tri fusion et du tri à bulles sur un tableau de taille n.

1. Quelle est la complexité en temps du tri fusion et du tri à bulles ?

2. Explique pourquoi le tri fusion est plus efficace que le tri à bulles pour de grands
tableaux.

Solution :

1. Complexité en temps :
o Le tri fusion a une complexité en temps de O(n log n) dans tous les cas
(meilleur, moyen et pire).
o Le tri à bulles a une complexité en temps de O(n²) dans le pire des cas,
et O(n) dans le meilleur cas (quand le tableau est déjà trié).
2. Explication :
o Le tri fusion est plus efficace que le tri à bulles pour de grands tableaux
car il divise le problème en sous-problèmes plus petits et utilise une
fusion efficace de ces sous-tableaux triés. Cela permet d'éviter les
comparaisons inutiles comme dans le tri à bulles, où chaque élément est
comparé plusieurs fois dans un grand nombre d'itérations.
o Le tri fusion fonctionne en O(n log n), ce qui est bien plus rapide que le
O(n²) du tri à bulles lorsque n devient grand.

Exercice 5 : Optimisation de la Mémoire dans le Tri Fusion

Enoncé :
Le tri fusion que nous avons vu utilise O(n) d'espace mémoire pour stocker les sous-
tableaux lors de la fusion. Existe-t-il une version optimisée en termes de mémoire du tri
fusion ? Si oui, explique comment.

Solution :

• Oui, il est possible d'optimiser la mémoire du tri fusion en utilisant le tri fusion
en place. Cependant, cela est plus complexe à implémenter. Une autre approche
consiste à éviter de créer de nouveaux tableaux pour chaque fusion en modifiant
les tableaux existants (en utilisant des indices pour garder trace des éléments).
• Cependant, dans la version classique, l'utilisation de O(n) d'espace mémoire est
nécessaire pour stocker les sous-tableaux lors de chaque fusion, ce qui est la
principale limitation de l'algorithme en termes de mémoire.

Conclusion

Voici un récapitulatif des éléments importants du tri fusion :

 1. Complexité en temps : O(n log n), même dans le pire des cas.
2. Avantages : Efficace pour de grands tableaux, stable, et adapté à des données
volumineuses.
3. Inconvénients : Utilise O(n) d'espace mémoire pour les sous-tableaux pendant la
fusion.
4. Optimisation mémoire : Le tri fusion en place peut réduire l'utilisation de la
mémoire, mais il est plus complexe à implémenter.

Le tri fusion est un algorithme de tri très performant pour des tableaux de taille
importante en raison de sa complexité logarithmique combinée à une efficacité linéaire
pour les étapes de fusion.

Exercice 1 : Implémentation du Tri à Bulles

Enoncé :
On te donne l'algorithme suivant pour trier un tableau arr avec le tri à bulles :

1. Quel est l'objectif de cet algorithme ?

2. Quelle est la complexité en temps de cet algorithme ?

Solution :

1. Objectif de l'algorithme :
L'objectif de cet algorithme est de trier un tableau arr en utilisant le tri à bulles.
Le principe du tri à bulles est de comparer chaque paire d'éléments adjacents et
de les échanger si l'élément de gauche est plus grand que celui de droite. Ce
processus est répété jusqu'à ce que le tableau soit entièrement trié.
2. Analyse de la complexité en temps :
o Boucles imbriquées :
L'algorithme utilise deux boucles imbriquées : la boucle externe s'exécute
n fois (où n est la taille du tableau), et la boucle interne compare les
éléments adjacents pour chaque itération de la boucle externe. Le nombre
de comparaisons effectuées à chaque itération diminue progressivement,
car après chaque passage, l'élément le plus grand "bulle" à sa position
finale.
o Pire des cas :
Dans le pire des cas, le tableau est inversé et chaque élément doit être
comparé avec chaque autre élément, ce qui donne une complexité O(n²).
o Meilleur des cas :
Si le tableau est déjà trié, une optimisation pourrait permettre de réduire
 le nombre de passages nécessaires, mais dans la version de base, la
complexité reste O(n²) dans tous les cas.

En résumé, la complexité en temps du tri à bulles est O(n²) dans le pire des cas, et O(n)
dans le meilleur cas (si une optimisation est ajoutée).

Exercice 2 : Complexité du Tri à Bulles dans le Pire Cas

Enoncé :
On te donne l'algorithme du tri à bulles. Quelle est la complexité en temps dans le pire
des cas ? Justifie ta réponse.

1. Quel est l'objectif de cet algorithme ?

2. Quelle est la complexité en temps dans le pire des cas ?

Solution :

1. Objectif de l'algorithme :
L'objectif de cet algorithme est de trier un tableau arr en utilisant le tri à bulles.
À chaque passage de la boucle externe, le plus grand élément "bulle" à sa
position correcte à la fin du tableau. Cela se fait par comparaison et échange des
éléments adjacents.
2. Analyse de la complexité en temps dans le pire des cas :
o Pire des cas :
Le pire des cas survient lorsque le tableau est trié dans l'ordre inverse.
Dans ce cas, l'algorithme devra effectuer un échange à chaque
comparaison dans chaque itération de la boucle interne.
o Nombre de comparaisons :
Pour chaque élément, la boucle interne effectue n-i-1 comparaisons, où i
est l'indice de la boucle externe. Le total des comparaisons sera donc de :

o
o Ce qui donne une complexité de O(n²) dans le pire des cas.

En résumé, la complexité en temps du tri à bulles dans le pire des cas est O(n²).
Exercice 3 : Meilleur Cas du Tri à Bulles avec Optimisation

Enoncé :
On te donne une version optimisée de l'algorithme du tri à bulles. Cette version ajoute
une condition pour arrêter le tri dès que le tableau est déjà trié après un passage :

1. Quelle est l'optimisation apportée ?

2. Quelle est la complexité en temps dans le meilleur cas après optimisation ?

Solution :

1. Optimisation :
L'optimisation consiste à ajouter un indicateur echange pour savoir si des
échanges ont eu lieu pendant une itération. Si aucun échange n'a été effectué,
cela signifie que le tableau est déjà trié, et l'algorithme peut s'arrêter
prématurément, économisant ainsi des itérations inutiles.
2. Complexité en temps dans le meilleur cas :
o Meilleur des cas :
Le meilleur des cas se produit lorsque le tableau est déjà trié. Dans ce cas,
l'algorithme effectue une première itération et constate qu'aucun échange
n'a eu lieu. Dès lors, il quitte la boucle grâce à la condition if not
echange: break.
o Cette optimisation permet de réduire la complexité dans le meilleur cas à
O(n), car l'algorithme s'arrête après une seule passe à travers le tableau.

En résumé, avec l'optimisation, la complexité en temps du tri à bulles dans le meilleur

cas est O(n).

Exercice 4 : Comparaison entre Tri à Bulles et Tri Fusion

Enoncé :
Compare les performances du tri à bulles et du tri fusion sur un tableau de taille n.
 1. Quelle est la complexité en temps du tri à bulles et du tri fusion ?
2. Explique pourquoi le tri fusion est plus efficace que le tri à bulles pour de grands
tableaux.

Solution :

1. Complexité en temps :
o Le tri à bulles a une complexité en temps de O(n²) dans le pire des cas.
o Le tri fusion a une complexité en temps de O(n log n) dans tous les cas
(meilleur, moyen et pire).
2. Explication :
o Le tri fusion est plus efficace que le tri à bulles pour de grands tableaux
car il divise le tableau en sous-tableaux plus petits et les fusionne de
manière ordonnée. À chaque niveau de récursion, il fusionne les sous-
tableaux en O(n), et il y a O(log n) niveaux de récursion, ce qui donne
une complexité de O(n log n).
o En revanche, le tri à bulles parcourt à plusieurs reprises tout le tableau
pour effectuer des échanges, ce qui peut entraîner un grand nombre de
comparaisons et d'échanges dans des tableaux de grande taille, donnant
une complexité de O(n²).

Conclusion : Le tri fusion est beaucoup plus efficace pour des tableaux de grande taille
que le tri à bulles en raison de sa complexité O(n log n) contre O(n²) pour le tri à bulles.

Exercice 5 : Explication du Comportement du Tri à Bulles sur un Tableau Presque

Trié

Enoncé :
Soit un tableau arr = [1, 2, 3, 5, 4], légèrement désordonné. Quelle sera la performance
du tri à bulles sur ce tableau ? Explique pourquoi.

1. Combien de passages le tri à bulles effectuera-t-il pour trier ce tableau ?

2. Quelle est la complexité en temps dans ce cas particulier ?

Solution :

1. Passages du tri à bulles :

o Le tri à bulles compare les éléments adjacents et les échange si
nécessaire. Dans ce cas, le tableau est presque trié, mais un seul échange
est nécessaire entre 5 et 4.
o Après un premier passage, le tableau devient [1, 2, 3, 4, 5]. L'algorithme
n'a plus besoin de faire d'autres échanges.
o Il effectuera donc 2 passages au total : un pour échanger les éléments et
un autre pour vérifier que tout est trié.
2. Complexité en temps dans ce cas particulier :
o Bien que le tableau soit presque trié, l'algorithme effectue toujours deux
passes et fait une comparaison pour chaque élément, ce qui entraîne une
complexité de O(n) pour ce cas particulier, où n est le nombre d'éléments.
 o Cependant, dans un cas plus général avec un tableau désordonné, la
complexité en temps serait O(n²) dans le pire des cas.

Conclusion

Voici un récapitulatif des points importants du tri à bulles :

1. Complexité en temps :
o Dans le pire des cas (tableau inversé) : O(n²)
o Dans le meilleur des cas (tableau déjà trié avec optimisation) : O(n)
o Dans la moyenne des cas : O(n²)
2. Avantages :
o Simple à implémenter et à comprendre.
o Efficace pour des petits tableaux ou des tableaux presque triés.
3. Inconvénients :
o Moins efficace pour des grands tableaux à cause de sa complexité
quadratique O(n²).

Le tri à bulles est souvent utilisé pour son aspect pédagogique, mais pour des
applications réelles avec des grandes quantités de données, des algorithmes plus
efficaces comme le tri fusion ou le tri rapide (quick sort) sont préférables.

Exercice 1 : Implémentation du Tri Rapide

Enoncé :
On te donne l'algorithme suivant pour trier un tableau arr avec le tri rapide :

1. Quel est l'objectif de cet algorithme ?

2. Quelle est la complexité en temps de cet algorithme ?

Solution :

1. Objectif de l'algorithme :
L'objectif de cet algorithme est de trier un tableau arr en utilisant le tri rapide.
Le principe du tri rapide est de choisir un pivot, puis de partitionner le tableau en
trois sous-tableaux :
 Un sous-tableau contenant les éléments inférieurs au pivot.
o
Un sous-tableau contenant les éléments égaux au pivot.
o
Un sous-tableau contenant les éléments supérieurs au pivot. Ensuite, on
o
applique récursivement le tri rapide sur les sous-tableaux gauche et droit,
puis on les concatène avec les éléments égaux au pivot pour obtenir le
tableau trié.
2. Analyse de la complexité en temps :
o Cas moyen :
Dans le cas moyen, le pivot divise le tableau presque en deux parties
égales. À chaque appel récursif, le tableau est divisé en deux sous-
tableaux de tailles environ égales. La partition des éléments prend O(n)
pour chaque niveau de récursion, et il y a log n niveaux de récursion en
moyenne. La complexité du tri rapide dans ce cas est donc O(n log n).
o Pire des cas :
Dans le pire des cas, si le pivot choisi est toujours le plus petit ou le plus
grand élément du tableau, le tableau ne sera pas du tout divisé en deux
parties égales. Dans ce cas, chaque appel récursif traite un sous-tableau
de taille n-1, ce qui donne une complexité de O(n²).
o Meilleur des cas :
Le meilleur des cas se produit lorsque le pivot divise toujours le tableau
en deux parties égales, ce qui donne également une complexité de O(n
log n).

En résumé, la complexité en temps du tri rapide est O(n log n) en moyenne, mais peut
atteindre O(n²) dans le pire des cas.

Exercice 2 : Complexité du Tri Rapide dans le Pire Cas

Enoncé :
On te donne l'algorithme du tri rapide. Quelle est la complexité en temps dans le pire des
cas ? Justifie ta réponse.

1. Quel est l'objectif de cet algorithme ?

2. Quelle est la complexité en temps dans le pire des cas ?

Solution :
 1. Objectif de l'algorithme :
L'objectif de cet algorithme est de trier un tableau arr en utilisant le tri rapide.
Le tableau est partitionné en trois sous-tableaux : ceux qui sont inférieurs au
pivot, égaux au pivot, et supérieurs au pivot. Ensuite, l'algorithme s'applique
récursivement sur les sous-tableaux gauche et droit.
2. Analyse de la complexité en temps dans le pire des cas :
o Pire des cas :
Dans le pire des cas, si le pivot choisi est toujours l'élément le plus petit
ou le plus grand du tableau (par exemple, lorsqu'on choisit toujours le
premier ou le dernier élément comme pivot), le tableau ne sera pas bien
partitionné. Cela signifie qu'un sous-tableau de taille n-1 et un autre de
taille 0 seront créés à chaque niveau récursif.
o Cela donne une complexité de O(n) pour la partition à chaque niveau de
récursion, mais il y aura n niveaux récursifs, ce qui donne une complexité
totale de O(n²) dans le pire des cas.

En résumé, la complexité en temps dans le pire des cas du tri rapide est O(n²).

Exercice 3 : Meilleur Cas du Tri Rapide

Enoncé :
Soit le tableau arr = [3, 2, 1, 5, 4]. Si tu utilises un pivot choisi au hasard, quel sera le
comportement du tri rapide ? Expliquer pourquoi.

1. Comment le pivot est choisi ?

2. Quelle est la complexité du tri rapide dans ce cas particulier ?

Solution :

1. Choix du pivot :
L'algorithme choisit le pivot comme étant l'élément du milieu du tableau. Dans
ce cas, le pivot choisi serait 1, car c'est l'élément du milieu de [3, 2, 1, 5, 4].
2. Comportement du tri rapide :
o Le tableau est partitionné en trois sous-tableaux :
▪ Gauche : les éléments inférieurs au pivot (aucun dans ce cas).
▪ Milieu : l'élément égal au pivot ([1]).
▪ Droite : les éléments supérieurs au pivot ([3, 2, 5, 4]).
o Ensuite, le tri rapide sera appliqué de manière récursive sur le sous-
tableau droit ([3, 2, 5, 4]).

Ce comportement est typique d'un bon choix de pivot qui divise efficacement le tableau
en deux parties équilibrées, ce qui conduit à une performance optimale.

3. Complexité du tri rapide dans ce cas particulier :

o Dans ce cas particulier, chaque partition divise efficacement le tableau en
deux sous-tableaux presque égaux. La complexité en temps du tri rapide
sera O(n log n), car chaque niveau de récursion divise le tableau en deux
 sous-tableaux de taille environ égale et la partition prend un temps
linéaire O(n).

En résumé, la complexité en temps du tri rapide dans le meilleur des cas est O(n log n).

Exercice 4 : Comparaison entre Tri Rapide et Tri à Bulles

Enoncé :
Compare les performances du tri rapide et du tri à bulles sur un tableau de taille n.

1. Quelle est la complexité en temps du tri rapide et du tri à bulles ?

2. Explique pourquoi le tri rapide est plus efficace que le tri à bulles pour de grands
tableaux.

Solution :

1. Complexité en temps :
o Le tri rapide a une complexité en temps de O(n log n) dans le cas
moyen et le meilleur cas, mais O(n²) dans le pire des cas.
o Le tri à bulles a une complexité en temps de O(n²) dans le pire des cas
(et dans la moyenne des cas), bien qu'il puisse atteindre O(n) si le tableau
est déjà trié et avec optimisation.
2. Explication :
o Le tri rapide divise le problème en sous-problèmes plus petits à chaque
étape, ce qui lui permet de traiter des tableaux plus grands plus
efficacement, en réduisant le nombre de comparaisons nécessaires. De
plus, le choix du pivot peut améliorer la partition et rendre l'algorithme
plus rapide que d'autres algorithmes comme le tri à bulles.
o Le tri à bulles, en revanche, compare chaque élément avec son voisin et
échange les éléments lorsque nécessaire. Cela implique un grand nombre
de comparaisons et d'échanges, surtout pour des tableaux non triés, ce qui
donne une complexité quadratique O(n²), même dans les meilleurs cas
(sauf optimisation).

Conclusion : Le tri rapide est beaucoup plus efficace que le tri à bulles pour des
tableaux de grande taille, en raison de sa complexité O(n log n) contre O(n²) pour le tri
à bulles.

Exercice 5 : Amélioration du Tri Rapide avec la Méthode de Partition

Enoncé :
On te donne la méthode de partition suivante qui choisit un pivot et réorganise les
éléments autour de ce pivot :
 1. Quelle est l'idée de la méthode de partition ?
2. Comment la méthode de partition améliore-t-elle la complexité du tri rapide ?

Solution :

1. Idée de la méthode de partition :

o La méthode de partition prend le dernier élément comme pivot et
réorganise les éléments du tableau en plaçant les éléments plus petits que
le pivot à gauche et les éléments plus grands à droite du pivot. Cela
permet de diviser efficacement le tableau en deux sous-tableaux à trier
récursivement.
2. Amélioration de la complexité du tri rapide :
o La méthode de partition permet de diviser le tableau en deux sous-
tableaux de tailles presque égales, ce qui améliore la performance du tri
rapide. Au lieu de simplement choisir un pivot au hasard, cette méthode
assure une partition plus équilibrée et contribue à réduire la probabilité de
tomber dans le pire des cas (O(n²)).

Conclusion

Voici un récapitulatif des points importants du tri rapide :

1. Complexité en temps :
o Dans le meilleur des cas : O(n log n)
o Dans le cas moyen : O(n log n)
o Dans le pire des cas : O(n²)
2. Avantages :
o Très rapide pour de grands tableaux dans la plupart des cas.
o Utilise la technique de division et conquête pour diviser efficacement le
problème.
3. Inconvénients :
o Complexité O(n²) dans le pire des cas, surtout si le pivot est mal choisi.
o Ne convient pas aux petits tableaux si on le compare à des algorithmes
plus simples comme le tri à bulles ou le tri par insertion.
Le tri rapide est l'un des algorithmes de tri les plus populaires en raison de ses bonnes
performances dans la plupart des cas, mais il faut prêter attention à son pire cas.

Exercice 1 : Complexité en espace d’un tableau statique

Enoncé :
Tu dois analyser la complexité en espace de la fonction suivante qui crée un tableau
statique et y insère des éléments :

1. Quelle est la complexité en espace de cette fonction ?

2. Explique pourquoi la taille du tableau influe sur la complexité en espace.

Solution :

1. Analyse de la complexité en espace :

o La fonction crée un tableau arr de taille num_elements. Ce tableau
occupe de l'espace mémoire.
o En Python, un tableau est une structure de données qui stocke une
collection d'éléments. Si num_elements est le nombre d'éléments à
stocker, le tableau nécessite une quantité d’espace mémoire
proportionnelle à num_elements.

Par conséquent, la complexité en espace de cette fonction est O(n), où n est le nombre
d'éléments dans le tableau (i.e., num_elements).

2. Pourquoi la taille du tableau influe sur la complexité en espace ?

o Le tableau nécessite une mémoire linéaire proportionnelle à sa taille. Plus
le nombre d’éléments à stocker est grand, plus l’espace nécessaire pour
stocker ces éléments augmente.
o La mémoire utilisée par le tableau augmente donc linéairement avec la
taille de l’entrée, ce qui conduit à une complexité en espace de O(n).

Exercice 2 : Complexité en espace d'un algorithme de tri par fusion

Enoncé :
On te donne l'algorithme suivant pour trier un tableau arr en utilisant le tri par fusion
(Merge Sort) :
 1. Quelle est la complexité en espace de cet algorithme ?
2. Expliquer pourquoi le tri par fusion nécessite un espace supplémentaire.

Solution :

1. Analyse de la complexité en espace :

o L'algorithme merge_sort divise récursivement le tableau en deux parties
jusqu'à ce que chaque partie contienne un seul élément. À chaque étape
de la fusion, de nouveaux tableaux temporaires left, right et result sont
créés.
o La complexité en espace dépend principalement des nouveaux tableaux
créés lors de chaque appel récursif et de la fusion des sous-tableaux.
o À chaque niveau de récursion, de nouveaux tableaux left, right et result
sont créés pour la fusion. Cela implique qu’à chaque niveau de la
récursion, l’espace mémoire nécessaire est proportionnel à la taille du
tableau.
o Comme la récursion divise le tableau en deux à chaque niveau, et qu'à
chaque niveau on crée des sous-tableaux de taille n, la complexité en
espace totale sera O(n), où n est la taille du tableau initial.
2. Pourquoi le tri par fusion nécessite-t-il un espace supplémentaire ?
o Le tri par fusion crée de nouveaux tableaux à chaque appel récursif pour
stocker les sous-tableaux divisés et les résultats de la fusion. Ce processus
de création de sous-tableaux entraîne une utilisation supplémentaire de
mémoire.
o En résumé, même si le tableau de départ est trié en place à l'aide de la
fusion, la méthode nécessite un espace supplémentaire pour stocker les
résultats intermédiaires. C’est ce qui conduit à une complexité en espace
de O(n).
Exercice 3 : Complexité en espace de l’algorithme de tri rapide

Enoncé :
On te donne l'algorithme suivant pour trier un tableau arr en utilisant le tri rapide
(Quick Sort) :

1. Quelle est la complexité en espace de cet algorithme ?

2. Explique pourquoi la complexité en espace du tri rapide est plus faible que celle
du tri par fusion.

Solution :

1. Analyse de la complexité en espace :

o L'algorithme de tri rapide utilise la récursion pour diviser le tableau en
sous-tableaux à chaque appel. Cependant, contrairement au tri par fusion,
les sous-tableaux ne sont pas créés par la récursion elle-même, mais sont
générés à chaque appel avec des compréhensions de liste (left, middle, et
right).
o Chaque appel à quick_sort crée de nouveaux tableaux pour chaque
partition (left, middle, right), mais ces partitions sont finalement
concaténées pour former le tableau trié. Cela signifie que la mémoire
nécessaire pour les sous-tableaux est proportionnelle à la taille du tableau
d’entrée à chaque niveau de récursion.
o La complexité en espace est dominée par la mémoire nécessaire pour
stocker ces sous-tableaux à chaque niveau de récursion. Ainsi, la
complexité en espace du tri rapide est O(n), car l'algorithme crée des
tableaux de taille n dans chaque appel récursif.
2. Pourquoi la complexité en espace du tri rapide est plus faible que celle du tri
par fusion ?
o Le tri rapide nécessite de la mémoire pour les sous-tableaux, mais
contrairement au tri par fusion, il ne crée pas de nouveaux tableaux pour
chaque fusion, car il effectue la partition du tableau en place (sans
nécessiter d’espace supplémentaire pour la fusion des sous-tableaux).
o Le tri par fusion, en revanche, crée de nouveaux tableaux lors de chaque
fusion, ce qui augmente la complexité en espace.
 o En résumé, bien que le tri rapide génère des sous-tableaux à chaque
niveau de récursion, il n’a pas besoin d’autant d’espace pour stocker des
résultats intermédiaires que le tri par fusion. La complexité en espace du
tri rapide est donc généralement plus faible.

Exercice 4 : Complexité en espace de la récursion

Enoncé :
Soit la fonction récursive suivante :

1. Quelle est la complexité en espace de cette fonction ?

2. Expliquer pourquoi la profondeur de la récursion influe sur la complexité en
espace.

Solution :

1. Analyse de la complexité en espace :

o La fonction factorielle est récursive. À chaque appel récursif, un nouvel
environnement d'exécution est créé pour stocker la valeur de n et la
valeur de la fonction factorielle(n-1).
o La complexité en espace est déterminée par la profondeur de la pile
d'exécution, c'est-à-dire le nombre d’appels récursifs qui sont empilés
avant d’atteindre la base de la récursion (ici, lorsque n atteint 1).
o La profondeur de la récursion est directement proportionnelle à la valeur
de n. À chaque appel récursif, la fonction appelle une nouvelle instance
de factorielle jusqu’à ce que n soit égal à 1, donc la profondeur est de
O(n).
o Par conséquent, la complexité en espace pour cette fonction récursive est
O(n), où n est le nombre d'appels récursifs empilés.
2. Pourquoi la profondeur de la récursion influe sur la complexité en espace ?
o Chaque appel récursif nécessite de l'espace mémoire pour stocker l'état
local de l'appel (les paramètres et variables locales). Plus la profondeur de
la récursion est grande, plus il faut de mémoire pour gérer cette pile
d'exécution.
o Dans ce cas, la pile d'exécution contient n appels récursifs, et donc la
complexité en espace de la récursion est O(n).

Exercice 5 : Complexité en espace pour les algorithmes de parcours d’un arbre

Enoncé :
Soit un arbre binaire de recherche (Binary Search Tree - BST). L'algorithme suivant
parcourt cet arbre en profondeur (DFS - Depth First Search) :

1. Quelle est la complexité en espace de cet algorithme ?

2. Comment la structure de l'arbre influe sur la complexité en espace de ce parcours
?

Solution :

1. Analyse de la complexité en espace :

o L’algorithme dfs (parcours en profondeur) utilise la pile d'exécution pour
gérer la récursion. À chaque appel récursif, un nouvel environnement est
créé pour chaque nœud de l'arbre.
o La profondeur de la récursion dépend de la hauteur de l’arbre. Si l'arbre
est parfaitement équilibré, la profondeur maximale de la récursion est
O(log n), où n est le nombre de nœuds.
o Si l'arbre est dégénéré (par exemple, une liste chaînée), la profondeur de
la récursion sera de O(n), où n est le nombre de nœuds de l'arbre.

Par conséquent, la complexité en espace est O(h), où h est la hauteur de l'arbre, ce qui
peut être O(log n) pour un arbre équilibré ou O(n) pour un arbre dégénéré.

2. Comment la structure de l'arbre influe sur la complexité en espace ?

o La hauteur de l’arbre joue un rôle clé dans la complexité en espace. Plus
l’arbre est déséquilibré, plus la profondeur de la pile récursive augmente,
ce qui augmente la complexité en espace.
o Un arbre équilibré aura une faible complexité en espace (proportionnelle
à O(log n)), tandis qu'un arbre dégénéré entraînera une complexité en
espace plus élevée (O(n)).

Conclusion

La complexité en espace est un concept clé pour analyser la mémoire utilisée par un
algorithme. Elle dépend de divers facteurs, tels que la taille des structures de données
manipulées, la profondeur de la récursion et la manière dont les données sont
partitionnées et traitées.