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é ... 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;i<t.length;i++){. 5. valeur = t[i];. 6. for(j=i;j>0 && t[j-1] > valeur;j--).
Part of the document
Corrigé du TD n°3
Exercice 1.
a. Temps d'exécution détaillé
|instruction |Temps d'exécution |
|1a |Tcharger + Tranger |
|1b |(2Tcharger + T< ) * (n+1) |
|1c |(2Tcharger + Tranger + T+) * n |
|2 |(2Tcharger + T+ + Tranger) * n |
|Total | |
c.Temps d'exécution détaillé
|instruction |Temps d'exécution |
|1a |Tcharger + Tranger |
|1b |(2Tcharger + T< ) * (n+1) |
|1c |(2Tcharger + Tranger + T+) * n |
|2a |(Tcharger + Tranger)* n |
|2b |?i=0 ((2Tcharger + T< ) * (n+1)) |
|2c |?i=0 ((2Tcharger + Tranger + T+) * n) |
|3 |?i=0((2Tcharger + T+ + Tranger) * n) |
|Total | | Exercice 2. Complexité du schéma de Horner
1. public class Exemple {
2. public static int horner(int[] t, int n, int x){
3. int s = t[n];
4. for(int i = n-1;i >= 0;--i)
5. s = s * x + t[i];
6. return s;
7. } Temps d'exécution détaillé
|instruction |Temps d'exécution |
|3 |3Tcharger + T[] + Tranger |
|4a |2Tcharger + T- + Tranger |
|4b |(2Tcharger + T 2n + 2 n-1 + . . . + 2 + 1 = ? 2i = 2n - 1 i=1