Corrigé du TD n°3 - LAMSADE
Travaux dirigés de structures des données et algorithmes n°3. Corrigé du TD n°3
. Exercice 1. a. Temps d'exécution détaillé. instruction. Temps d'exécution. 1a. T
charger + Tranger. 1b. (2Tcharger + T< ) * (n+1). 1c. (2Tcharger + Tranger + T+) *
n. 2. (2Tcharger + T+ + Tranger) * n. Total. c.Temps d'exécution détaillé ...
part of the document
int s = t[n];
4. for(int i = n-1;i >= 0;--i)
5. s = s * x + t[i];
6. return s;
7. }
Temps dexécution détaillé
instructionTemps dexécution33Tcharger + T[] + Tranger4a2Tcharger + T- + Tranger4b(2Tcharger + T O(n)
Exercice 3. Complexité du tri par insertion
1. public class Exemple {
2. static void triInsertion(int[] t){
3. int valeur,i,j;
4. for(i=1;i0 && t[j-1] > valeur;j--)
7. t[j] = t[j-1];
8. t[j] = valeur;
9. }
10. }
Temps dexécution détaillé
instructionTemps dexécution4aTcharger + Tranger4b(2Tcharger + T< )x n4c(2Tcharger + Tranger + T-)x (n-1)5(3Tcharger + Tranger+ T[])x (n-1)6a(Tcharger + Tranger)x (n-1)6b(7Tcharger + 2T
