193 lines
6.8 KiB
Markdown
193 lines
6.8 KiB
Markdown
#### **Exercice 1**
|
||
|
||
1. **`function_1(tableau1, tableau2)`** :
|
||
Dans cette fonction, il y a deux boucles imbriquées : la première parcourt tous les éléments de `tableau1` (de taille \(n\)), et pour chaque élément, la deuxième boucle parcourt `tableau2` (de taille \(m\)).
|
||
Dans le pire des cas, si aucun élément ne correspond (ou si le `break` n'est jamais atteint), chaque élément de `tableau1` sera comparé à tous les éléments de `tableau2`.
|
||
Donc, la complexité de cette fonction est \( O(n \cdot m) \).
|
||
|
||
2. **`function_2(x)`** :
|
||
Ici, on a une boucle `while` qui s’exécute \(x\) fois. À chaque itération, on effectue une addition et une décrémentation, qui prennent toutes les deux un temps constant.
|
||
Du coup, la complexité est proportionnelle à \(x\), donc \( O(x) \).
|
||
|
||
3. **`function_3(x)`** :
|
||
Cette fonction contient uniquement des blocs `if` indépendants, qui s’exécutent chacun au maximum une seule fois. Il n’y a pas de boucle, donc chaque opération est constante.
|
||
La complexité est donc \( O(1) \), car c’est constant peu importe la valeur de \(x\).
|
||
|
||
---
|
||
|
||
#### **Exercice 2**
|
||
|
||
Pour analyser la complexité de la fonction **`sort_students`**, on décompose chaque étape :
|
||
|
||
1. **Boucle externe sur les grades** :
|
||
La boucle externe parcourt tous les grades des étudiants, soit \( \text{grades\_number} \) itérations.
|
||
|
||
2. **Allocation dynamique des notes** :
|
||
L’allocation du tableau `grades` est faite avec `malloc`, qui est supposée avoir une complexité \( O(1) \). Cela n’affecte donc pas significativement la complexité globale.
|
||
|
||
3. **Copie des notes des étudiants** :
|
||
Dans la boucle interne :
|
||
```c
|
||
for(j = 0; j < students_number; j++) {
|
||
grades[j] = students_array[j][i];
|
||
}
|
||
```
|
||
on copie les notes des \( \text{students\_number} \) étudiants, ce qui prend \( O(\text{students\_number}) \) par itération de la boucle externe.
|
||
|
||
4. **Tri des notes avec `bubblesort`** :
|
||
La fonction `bubblesort` trie un tableau de taille \( \text{students\_number} \), avec une complexité \( O(\text{students\_number}^2) \).
|
||
|
||
5. **Trouver le rang de chaque étudiant** :
|
||
Ensuite, dans cette boucle interne :
|
||
```c
|
||
for(j = 0; j < students_number; j++) {
|
||
students_rank[j][i] = find_rank_student(students_array[j][i], grades, students_number);
|
||
}
|
||
```
|
||
on appelle `find_rank_student` pour chaque étudiant. Cette fonction effectue :
|
||
- Un tri par bulles \( O(\text{students\_number}^2) \),
|
||
- Une recherche pour trouver le rang, qui prend \( O(\text{students\_number}) \).
|
||
|
||
Donc, chaque appel à `find_rank_student` a une complexité totale de \( O(\text{students\_number}^2) \), et cette fonction est appelée \( \text{students\_number} \) fois par itération de la boucle externe. Cela donne une complexité \( O(\text{students\_number}^3) \) par itération de la boucle externe.
|
||
|
||
6. **Libération de mémoire** :
|
||
Enfin, la mémoire allouée pour `grades` est libérée avec `free`, ce qui est une opération \( O(1) \).
|
||
|
||
### Complexité totale :
|
||
La boucle externe s’exécute \( \text{grades\_number} \) fois, et la partie la plus coûteuse de la boucle interne est \( O(\text{students\_number}^3) \). La complexité globale de la fonction est donc :
|
||
\[
|
||
O(\text{grades\_number} \cdot \text{students\_number}^3)
|
||
\]
|
||
|
||
### Conclusion :
|
||
La fonction **`sort_students`** a une complexité algorithmique de
|
||
\[
|
||
O(\text{grades\_number} \cdot \text{students\_number}^3)
|
||
\]
|
||
|
||
|
||
---
|
||
|
||
|
||
#### **Exercice 3**
|
||
|
||
|
||
### **Algorithme proposé**
|
||
|
||
1. **Tri des sous-dimensions** :
|
||
- Si on est sur un tableau 1D (le plus bas niveau), on le trie avec un tri par insertion.
|
||
|
||
2. **Calcul des sommes des sous-dimensions** :
|
||
- Pour chaque sous-tableau, on calcule la somme des valeurs pour s’en servir comme critère de tri.
|
||
|
||
3. **Tri des sous-dimensions par leurs sommes** :
|
||
- On trie les sous-dimensions avec un tri par insertion basé sur les sommes calculées.
|
||
|
||
4. **Répétition pour les autres dimensions** :
|
||
- On applique ces étapes de façon récursive à chaque niveau du tableau.
|
||
|
||
|
||
|
||
### **Implémentation**
|
||
|
||
Voici l'algorithme en Python :
|
||
|
||
```python
|
||
# Fonction pour trier un tableau 1D avec un tri par insertion
|
||
def insertion_sort(arr):
|
||
for i in range(1, len(arr)):
|
||
key = arr[i]
|
||
j = i - 1
|
||
# Déplacement des éléments plus grands que key
|
||
while j >= 0 and arr[j] > key:
|
||
arr[j + 1] = arr[j]
|
||
j -= 1
|
||
arr[j + 1] = key
|
||
|
||
# Fonction pour trier un tableau multidimensionnel récursivement
|
||
def recursive_sort(T):
|
||
# Si c'est un tableau 1D, on le trie
|
||
if not isinstance(T[0], list):
|
||
insertion_sort(T)
|
||
return T
|
||
|
||
# Trier chaque sous-dimension
|
||
for i in range(len(T)):
|
||
T[i] = recursive_sort(T[i])
|
||
|
||
# Calculer les sommes des sous-dimensions
|
||
sums = [sum(sum(val) if isinstance(val, list) else val for val in sublist) for sublist in T]
|
||
|
||
# Trier les sous-dimensions en fonction de leurs sommes
|
||
for i in range(1, len(T)):
|
||
key_sum = sums[i]
|
||
key_sublist = T[i]
|
||
j = i - 1
|
||
while j >= 0 and sums[j] > key_sum:
|
||
sums[j + 1] = sums[j]
|
||
T[j + 1] = T[j]
|
||
j -= 1
|
||
sums[j + 1] = key_sum
|
||
T[j + 1] = key_sublist
|
||
|
||
return T
|
||
|
||
# Exemple avec un tableau 2D
|
||
tableau = [[0, 3, 2], [9, 4, 5], [4, 1, 3]]
|
||
resultat = recursive_sort(tableau)
|
||
print(resultat) # Résultat attendu : [[0, 2, 3], [1, 3, 4], [4, 5, 9]]
|
||
```
|
||
|
||
|
||
### **Exemple d’exécution**
|
||
|
||
Prenons le tableau suivant :
|
||
\[ [ [0, 3, 2], [9, 4, 5], [4, 1, 3] ] \]
|
||
|
||
1. **Trier chaque ligne** :
|
||
- Première ligne : \( [0, 3, 2] \rightarrow [0, 2, 3] \)
|
||
- Deuxième ligne : \( [9, 4, 5] \rightarrow [4, 5, 9] \)
|
||
- Troisième ligne : \( [4, 1, 3] \rightarrow [1, 3, 4] \)
|
||
\[
|
||
[ [0, 2, 3], [4, 5, 9], [1, 3, 4] ]
|
||
\]
|
||
|
||
2. **Calculer les sommes** :
|
||
- \( [0, 2, 3] \rightarrow 5 \)
|
||
- \( [4, 5, 9] \rightarrow 18 \)
|
||
- \( [1, 3, 4] \rightarrow 8 \)
|
||
|
||
3. **Trier les lignes en fonction des sommes** :
|
||
\[
|
||
[ [0, 2, 3], [1, 3, 4], [4, 5, 9] ]
|
||
\]
|
||
|
||
|
||
### **Complexité**
|
||
|
||
#### Analyse :
|
||
|
||
1. **Tri des tableaux 1D** :
|
||
- Pour \( M \) éléments, le tri par insertion a une complexité de \( O(M^2) \).
|
||
|
||
2. **Tri des sous-tableaux (dimensions \( N > 1 \))** :
|
||
- Chaque sous-tableau contient \( M^{N-1} \) éléments. Trier ces sous-tableaux coûte \( O(M^{N-1} \cdot M^{N-1}) = O(M^{2(N-1)}) \).
|
||
|
||
3. **Calcul des sommes** :
|
||
- Calculer les sommes pour \( M^{N-1} \) sous-tableaux coûte \( O(M^N) \).
|
||
|
||
4. **Complexité totale** :
|
||
- L'algorithme s’applique de façon récursive sur \( N \) dimensions. La partie dominante vient du tri des sous-tableaux les plus grands :
|
||
\[
|
||
T(N, M) = O(M^{2N-2})
|
||
\]
|
||
|
||
|
||
|
||
### **Conclusion**
|
||
|
||
- - La complexité globale est
|
||
\[
|
||
O(M^{2N-2})
|
||
\]
|