forked from menault/TD4_DEV51_Qualite_Algo
96 lines
2.6 KiB
Markdown
96 lines
2.6 KiB
Markdown
# Ex 2
|
||
|
||
```py
|
||
def function_1(tableau1, tableau2):
|
||
presentDansDeuxListes = 0
|
||
for nombre1 in tableau1: # O(n)
|
||
for nombre2 in tableau2: # O(n²)
|
||
if nombre1 == nombre2:
|
||
presentDansDeuxListes += 1
|
||
break
|
||
return presentDansDeuxListes
|
||
```
|
||
|
||
cette fonction à une complexité de **O(n²)**
|
||
|
||
---
|
||
|
||
```py
|
||
def function_2(x):
|
||
valeur = 0
|
||
while x > 0: # O(n)
|
||
valeur = valeur + x
|
||
x -= 1 # si x = 300, on passe dans le while 300 fois
|
||
return valeur
|
||
```
|
||
|
||
cette fonction a une complexité de **O(n)**
|
||
|
||
---
|
||
|
||
```py
|
||
def function_3(x):
|
||
valeur = 0
|
||
if x < 0:
|
||
valeur = -x
|
||
if x == 0:
|
||
pass
|
||
if x > 0:
|
||
valeur = x
|
||
return valeur
|
||
```
|
||
|
||
cette fonction a une complexité de **O(1)**
|
||
|
||
|
||
# Ex 3
|
||
|
||
```py
|
||
def entree_tri_fusion_multi(tab):
|
||
tab = [tri_fusion(sub_tab) for sub_tab in tab] # Appliquer le tri fusion à chaque sous-tableau
|
||
return sorted(tab, key=sum) # Trier les sous-tableaux par la somme de leurs éléments
|
||
|
||
def tri_fusion(tab):
|
||
if len(tab) <= 2:
|
||
if tab[0] > tab[-1]:
|
||
return tab[::-1]
|
||
return tab
|
||
mid = len(tab) // 2 # Trouver le milieu du tableau
|
||
left = tri_fusion(tab[:mid]) # Diviser et trier la moitié gauche
|
||
right = tri_fusion(tab[mid:]) # Diviser et trier la moitié droite
|
||
return fusion(left, right) # Fusionner les deux moitiés triées
|
||
|
||
def fusion(left, right):
|
||
result = []
|
||
i = j = 0
|
||
while i < len(left) and j < len(right): # Tant qu'il reste des éléments dans les deux sous-tableaux
|
||
if left[i] < right[j]: # Comparer les éléments des deux sous-tableaux
|
||
result.append(left[i]) # Ajouter l'élément de gauche s'il est plus petit
|
||
i += 1
|
||
else:
|
||
result.append(right[j]) # Ajouter l'élément de droite sinon
|
||
j += 1
|
||
result.extend(left[i:]) # Ajouter les éléments restants de gauche
|
||
result.extend(right[j:]) # Ajouter les éléments restants de droite
|
||
return result
|
||
```
|
||
|
||
---
|
||
|
||
```py
|
||
from tri_fusion import entree_tri_fusion_multi
|
||
|
||
tab = [[38, 27, 43, 3, 9, 82, 10], [1, 2, 3], [5, 4, 6], [12, 11]]
|
||
sorted_tab = entree_tri_fusion_multi(tab)
|
||
print("Tableau trié :", sorted_tab)
|
||
```
|
||
|
||
```bash
|
||
Tableau trié : [[1, 2, 3], [4, 5, 6], [11, 12], [3, 9, 10, 27, 38, 43, 82]]
|
||
```
|
||
|
||
La complexité de l’algorithme est **O(k · n log n)**, où ***k*** est le nombre de sous-tableaux et ***n*** leur taille moyenne.
|
||
Chaque sous-tableau est trié par tri fusion en **O(n log n)**, puis la liste des sous-tableaux est triée par somme en **O(k log k)**, ce qui est négligeable devant le terme dominant.
|
||
|
||
|