Algorithmique

Compromis espace/temps

Oui, bien sûr.

Solution 1 :

	A	B	tmp
au départ :	5	12	?
tmp <--- A	5	12	5
A <--- B	12	12	5
B <--- tmp	12	5	5

Mais savez-vous que l'on peut choisir entre deux compromis différents :

• solution 1 : privilégier le temps d'exécution au détriment de la place mémoire en utilisant une 3^ème variable intermédiaire
• solution 2 : privilégier la place mémoire au détriment du temps d'exécution en effcetuant des opérations uniquement sur les 2 variables

Donc comment faire sans 3^ème variable ?

Cherchez un peu avant de regarder la solution ...

Solution 2 :

		A	B
0.	au départ :	5	12
1.	A <--- A + B	17	12
2.	B <--- A - B	17	5
3.	A <--- A - B	12	5

Démonstration en affectant les indices des lignes ci-dessus aux valeurs successives des deux variables :

0.	A0	B0
1.	A1 <--- A0 + B0	B1 = B0
2.	A2 = A1 = A0 + B0	B2 <--- A1 - B1 = A0 + B0 - B0 = A0
3.	A3 <--- A2 - B2 = A0 + B0 - A0 = B0	B3 = B2 = A0

Attention !

La solution 2 ne fonctionne que pour des variables d'un type supportant l'addition et la soustraction sans perte de précision, et pour des valeurs dont la somme ou la différence ne dépassent pas la valeur maximale représentable pour ce type.