Corrigé du TD n°3 - LAMSADE
MI2E 1ère année Semaine du 27 Février 2006. Structures de données et
algorithmes. B. Quement. Corrigé du TD n°3. Exercice 1. a. 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
