64 lines
1.7 KiB
Markdown
64 lines
1.7 KiB
Markdown
# RAPPORT
|
|
|
|
## EXO2
|
|
|
|
- **function_1(tableau1, tableau2)** :
|
|
- **Complexité algorithmique** : O(n * m)
|
|
- Dans le pire cas, où `n` est la taille du tableau 1 et `m` la taille du tableau 2.
|
|
|
|
- **function_2(x)** :
|
|
- **Complexité algorithmique** : O(x)
|
|
- La boucle `while` fait `x` itérations, et `x` est décrémentée de 1 jusqu'à 0.
|
|
|
|
- **function_3(x)** :
|
|
- **Complexité algorithmique** : O(1)
|
|
- En fonction de la valeur de `x`, une des trois conditions exécute une opération simple.
|
|
|
|
---
|
|
|
|
## EXO3
|
|
|
|
Pour cette fonction, on a :
|
|
|
|
- **La première boucle for** : O(g)
|
|
- **Malloc** : O(1)
|
|
- **Deuxième boucle for** : O(g * n)
|
|
- **Bubblesort** : O(g * n²)
|
|
- **Free** : O(1)
|
|
- **find_rank_student** : O(g * n²) pour Bubblesort + O(g * n) : O(g * n^3)
|
|
|
|
**Simplification :**
|
|
- On peut enlever les O(1) et conserver la complexité la plus élevée, donc O(g * n^3).
|
|
|
|
**Complexité algorithmique pour sort_student :** O(g * n^3)
|
|
|
|
---
|
|
|
|
## EXO4
|
|
|
|
Voici le code :
|
|
|
|
```python
|
|
def tri(t):
|
|
for tab in t:
|
|
for i in range(len(tab)):
|
|
for j in range(len(tab) - 1):
|
|
if tab[j] > tab[j + 1]:
|
|
tab[j], tab[j + 1] = tab[j + 1], tab[j]
|
|
|
|
for i in range(len(t)):
|
|
for j in range(len(t) - 1):
|
|
if t[j][0] > t[j + 1][0]:
|
|
t[j], t[j + 1] = t[j + 1], t[j]
|
|
|
|
print(t)
|
|
|
|
tri([[3, 9, 6], [9, 3, 8], [10, 67, 55]])
|
|
```
|
|
|
|
Complexité algorithmique de ma fonction tri() :
|
|
|
|
- Pour m éléments, la complexité algorithmique de chaque sous-liste est O(m²), multipliée par le nombre de sous-listes, cela fait : O(n * m²).
|
|
- Pour le tri final, la complexité algorithmique est O(n²).
|
|
|
|
On garde la plus élevée, donc pour ma fonction : O(n * m²) + O(n²). |