Correction TD2
Exercice 1 :
1) Int max(int T[],int n){
int m=T[0];
int i;
for (i=1;i<=n-1;i++){
if(m<T[i]){m=T[i];}
}
return m;
}
2) C(n)=n-1=O(n)
3) Pour montrer que notre algorithme est optimal il faut
montrer que tout algorithme qui cherche le max de T
effectue au moins n-1 comparaison.
Soit P un algorithme qui cherche le max de T
- P doit visiter toutes les cases de T car sinon une case
non visitée peut contenir une valeur plus grande que
la valeur retournée par P
- P retourne le max de T trouvée à une position i
Pour les n-1 valeurs restantes ( !=i), elles ne sont pas
retournées comme max car elles ont dû perdre une
comparaison avec au moins une autre valeur de T.
P a effectué au moins n-1 comparaisons
Ainsi notre algorithme est optimal
Exercice 2 :
1) La boucle for compte N itérations et pour chaque
itération on a une seule opération
=> C(N)=N=O(N)
2) Méthode exacte
i=1 1op
i=2 2op
i=3 3op
…
i=N Nop
=> c(N)=1+2+3+…+N=N(N+1)/2=O(N²)
Rappel : Suites arithmétiques
Soit U une suite arithmétique de raison r et de 1er terme
U0, alors on a :
- Un=Un-1 + r
- Un=U0+n*r
- U0+U1+…+Un-1=n(U0+Un-1)/2
Cas particulier :
1+2+3+...+n=n(n+1)/2
Méthode de la majoration
1er boucle for : N itérations
2ème boucle for : i itérations <=N
C(N)<=N*N<=N²
C(N)=O(N²)
Remarque : En général les deux méthodes ne donnent pas le
même résultat la première méthode est plus précise et n’est
applicable que si la somme à calculer est remarquable. Pour la
deuxième méthode elle est toujours facile à appliquer mais
elle n’est pas précise.
3) Le nombre d’itérations de la boucle « while » est le
nombre de multiplication successives par 2 à effectuer
pour aller de 1 à N
=> la boucle « while » compte log2(N) itérations
=> C(N)=log2(N)=O(log N)
4) Boucle for : N itérations
Boucle while : log2(N) itérations
=> C(N)=NLog2(N)=O(NlogN)
5) Méthode de la majoration :
Boucle while : log2(N) itérations
Boucle for : i itérations <=2*(N-1) (on peut majorer par
2n)
C(N)<=2(n-1)Log2(N)
=> C(N)=O(NlogN)
Méthode exacte :
i=1 => i=2 et on exécute 2 op
i=2 => i=4 et on exécute 4 op
i=4 => i=8 et on exécute 8 op
.
.
.
i=2^p<n => i=2^(p+1) et on exécute 2^(p+1) op
p+1 est le plus petit entier tel que 2^(p+1) >=n
Remarque : par définition p+1=partie entière supérieure
de n.
Ainsi C(n)=2+4+8+….+2^(p+1)
Rappel : Suites géométriques
Soit U une suite géométriques de raison q et de 1er
terme U0 alors on a :
- Un=Un-1 * q
- Un=U0*q^n
- U0+U1+….+Un-1=U0(1-q^n)/(1-q)
D’où C(n)=2*(1-2^(p+1))/(1-2)=2*(2^(p+1)-1)
<=2*(2*2^p-1) on a 2^p<n
<=2*(2n-1)
Ainsi C(n)=O(n)
Remarque on voit ici que les deux méthodes n’ont pas
donné le même résultat, la méthode de la majoration à
surclassé notre algorithme.
6) La valeur de i après la 1er boucle for est
i=1*2*2*2*…*2 n fois
=2^n
La 2ème boucle for compte 2^n itérations
C(n)=2^n=O(2^n)
7) Méthode de la majoration:
1er boucle for : n itérations
3ème boucle for : 2^k itérations <=2^n
C(n)<=n*2^n
C(N)=O(n*2^n)
Méthode exacte :
for k=1 to n do
2^k opérations
endfor
C(n)=2^1+2^2+2^3+….2^n=2*(1-2^n)/(1-2)
=> C(n)=2(2^n-1)=O(2^n)
Exercice 2 (Examen 2014)
1) La boucle while compte log3(n) itérations et
pour chaque itération on a deux opérations
C(n)=2*log3(n)=O(logn)
2) 1er boucle for : n itérations
2ème boucle for : n²-i+1 <=n²+1 itérations
=> c(n)<=n*(n²+1)
C(n)=O(n^3)
3 ) 1er boucle for : n itérations
2ème boucle for : i²<=n² itérations
3ème boucle for : j<=i²<=n² itérations
=> C(n)<=n*n²*n²<=n^5 =>C(n)=O(n^5)
Exercice 1 (Examen 2014)
1) La fonction permet de remplacer les slashs consécutifs
par un simple slash
2) C’est la chaine composée par n slash
3) Boucle while O(n)
Boucle for O(n)
Les deux boucles sont imbriquées
C(n)=O(n*n)=O(n^2)
