Newer
Older
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
# Complexité des algorithmes 2
## Analyse du tri par fusion
Un algorithme basé sur le principe « diviser pour régner » :
* Diviser le problème initial en plusieurs sous-problèmes plus faciles à résoudre (de façon récursive).
* Combiner les solutions des sous-problèmes pour obtenir la solution du problème initial.
```
ALGORITHME TriFusion(a, debut, fin)
ENTRÉE :
a - un tableau
debut - indice du premier élément
fin - indice du dernier élément
SORTIE :
Le sous-tableau a[debut ... fin] est trié
TAILLE :
fin - debut + 1
DEBUT
SI debut < fin ALORS
milieu <- (debut + fin) / 2
TriFusion(a, debut, milieu)
TriFusion(a, milieu + 1, fin)
Fusion(a, debut, milieu, fin)
FINSI
FIN
```
```
ALGORITHME Fusion(a, debut, milieu, fin)
ENTRÉE :
a - un tableau
debut <= milieu <= fin : indices dans le tableau
les sous-tableaux a[debut ... milieu] et a [milieu + 1 ... fin] sont triés
SORTIE :
Le sous-tableau a[debut ... fin] est trié
TAILLE :
fin - debut + 1
DEBUT
i <- debut
j <- milieu + 1
k <- 0
TANTQUE i <= milieu et j <= fin FAIRE
SI a[i] < a[j] ALORS
tmp[k] <- a[i]
i <- i + 1
SINON
tmp[k] <- a[j]
j <- j + 1
FINSI
k <- k + 1
FINTANTQUE
TANTQUE i <= milieu
tmp[k] <- a[i]
i <- i + 1
k <- k + 1
FINTANTQUE
TANTQUE j <= fin
tmp[k] <- a[j]
j <- j + 1
k <- k + 1
FINTANTQUE
POUR i de debut à fin FAIRE
a[i] <- tmp[i - debut]
FINPOUR
FIN
```
Soit $`T(n)`$ le temps d'exécution de l'algorithme `TriFusion` pour une entrée de taille $`n`$. On peut facilement voir que
```math
T(n) =
\begin{cases}
c & \text{pour $n = 1$} \\
2 T(\frac{n}{2}) + T_\text{f}(n) & \text{pour $n > 1$}
\end{cases}
```
où $`T_\text{f}(n)`$ est le temps d'exécution de l'algorithme `Fusion`. En ce qui concerne ce dernier, on constate que dans les trois boucles `TANTQUE` il y a une itération par élément du tableau. Pareil pour la dernière boucle `POUR`. On a donc
```math
T_\text{f}(n) = \Theta(n) = a n + b
```
---
**Exercice** Montrer que $`T(n) = \Theta(n \log n)`$.
* Commencer par poser $`n = 2^k`$
* Montrer par récurrence que
```math
T(2^k) = 2^k c + a k 2^k + (2^k - 1) b
```
---
À noter qu'on peut omettre la base du logarithme car le changement de base revient à la multiplication par une constante.
---
**Exercice** Nous avons deux ordinateurs :
* Ordinateur A capable d'exécuter $`10^9`$ (1 milliard) d'instructions par seconde
* Ordinateur B capable d'exécuter $`10^7`$ (10 millions) d'instructions par seconde
A est donc 100 fois plus rapide que B.
* Tri par insertion implémenté en un langage de bas niveau et très optimisé. Pour une entrée de taille $`n`$ il exécute $`2 n^2`$ instructions au pire des cas.
* Tri par fusion implémenté en un langage interprété et pas du tout optimisé. Il exécute $`50 n \log_2 n`$ instructions pour une entrée de taille $`n`$.
On exécute le tri par insertion sur l'ordinateur rapide A et le tri par fusion sur l'ordinateur lent B.
Estimer le temps d'exécution des deux algorithmes pour des tableaux de taille 1 million et 10 millions.