forked from menault/TD4_DEV51_Qualite_Algo
99 lines
3.4 KiB
Markdown
99 lines
3.4 KiB
Markdown
|
# Rapport TD4 :
|
||
|
|
|
||
|
|
## Exercice 2 :
|
||
|
|
1) Fonction n°1 : complexité algorithmique O(n*m) <br>
|
||
|
|
(avec n = len(tab1) et m = len(tab2) ). Car l'on parcours deux tableau et que l'on compare ces derniers
|
||
|
|
|
||
|
|
2) Fonction n°2 : complexité algorithmique O(n)
|
||
|
|
<br>
|
||
|
|
Car ici on boucle tant que x > 0 et l'on retire 1 à chaque itérantion , donc la boucle est effectué x fois
|
||
|
|
|
||
|
|
3) Fonction n°3 : complexité algorithmique de O(1)
|
||
|
|
<br>
|
||
|
|
Car la fonction vas prendre la valeur de x et effectuer une seule opération en fontion de cette dernière.
|
||
|
|
|
||
|
|
## Exercice 3 :
|
||
|
|
|
||
|
|
Dans un premier temps, décomposon le code.<br>
|
||
|
|
- on retrouve au tout début du code une boucle :
|
||
|
|
```
|
||
|
|
for(i = 0; i < grades_number; i++){
|
||
|
|
int *grades = (int*) malloc(students_number * sizeof(int));
|
||
|
|
|
||
|
|
```
|
||
|
|
la complexité est donc de O(n)<br>
|
||
|
|
(Ou n = grades_number)
|
||
|
|
|
||
|
|
- dans un second temps, on peut retrouver cette partie de code :
|
||
|
|
```
|
||
|
|
for (j = 0; j < students_number; j++)
|
||
|
|
{
|
||
|
|
grades[j] = students_array[j][i];
|
||
|
|
}
|
||
|
|
```
|
||
|
|
Ici la complexité est de O(m) car on boucle sn fois.<br>
|
||
|
|
(Ou m = student_number)
|
||
|
|
|
||
|
|
- troisième portion de code :
|
||
|
|
```
|
||
|
|
bubblesort(grades, students_number);
|
||
|
|
|
||
|
|
```
|
||
|
|
Comme bubblesort parcours le tableau pour le trier chaque élément doit être comparé au autre. La complexité est donc de O(m^2)
|
||
|
|
|
||
|
|
- Quatrième partie de code :
|
||
|
|
```
|
||
|
|
for (j = 0; j < students_number; j++)
|
||
|
|
{
|
||
|
|
students_rank[j][i] = find_rank_student(students_array[j][i], grades, students_number);
|
||
|
|
}
|
||
|
|
```
|
||
|
|
Ici il nous faut la complexité algorythmique de find_rank_student, cette dernière est de O(m^2), donc la complexité de cette boucle est de O(m)*O(m^2)=O(m^3)
|
||
|
|
|
||
|
|
- Dernière partie de code :
|
||
|
|
```
|
||
|
|
free(grades);
|
||
|
|
```
|
||
|
|
Ici la complexité algorithmique est de O(1)
|
||
|
|
|
||
|
|
Donc la complexité algorithmique de cette fonction est de : O(n)*(O(m)+O(m²)+O(m^3)+O(1)) <br>
|
||
|
|
|
||
|
|
On obtient donc la complexité suivante : O(n*m^3)
|
||
|
|
|
||
|
|
|
||
|
|
## Exercice 4 :
|
||
|
|
(voir *Ex4_sort.py*)<br>
|
||
|
|
|
||
|
|
|
||
|
|
Complexité algorithmique :
|
||
|
|
- Complexité de *bubblesort_array* : O(n^2) car chaque élément à des chance d'être déplacé plusieurs fois.
|
||
|
|
|
||
|
|
- Complexité de *bubblesort_multi_array* :
|
||
|
|
- première partie de code :
|
||
|
|
```
|
||
|
|
for subarray in array:
|
||
|
|
bubblesort_array(subarray)
|
||
|
|
```
|
||
|
|
ici la complexité algorithmique est de O(n*m^2) (où n = longueur du tableau pricipal et m = taille des sous taableaux)
|
||
|
|
|
||
|
|
- seconde partie de code :
|
||
|
|
```
|
||
|
|
while (swap > 0):
|
||
|
|
swap = 0
|
||
|
|
for i in range(1, len(array)):
|
||
|
|
if sum(array[i-1]) > sum(array[i]):
|
||
|
|
temp = array[i-1]
|
||
|
|
array[i-1] = array[i]
|
||
|
|
array[i] = temp
|
||
|
|
swap += 1
|
||
|
|
```
|
||
|
|
ici la complexité algorithmique est de O(n^2*m)
|
||
|
|
|
||
|
|
- calcul final :
|
||
|
|
la complexité algorithmique est donc de O(n^2 * m + n * m2). cenpendant la complexité dépend donc des tailles du tableau et sous-tableau. Nous avons donc trois possibilité :
|
||
|
|
- première possibilité : n > m
|
||
|
|
Alors (n^2 * m) > (n * m^2), donc la complexité algorithmique est de O(n^2 * m)
|
||
|
|
- seconde possibilité : m > n
|
||
|
|
Donc (n * m^2) > (n^2 * m), donc la complexité algorithmique est de O(n*m^2)
|
||
|
|
- dernière possibilité : n = m
|
||
|
|
Ici si n = m alors la complexité algorithmique est bien de O(n^2 * m + n * m^2)
|