forked from menault/TD4_DEV51_Qualite_Algo
30 lines
1.2 KiB
Markdown
30 lines
1.2 KiB
Markdown
# TD4: Complexité algorithmique
|
|
|
|
## Exercice 2
|
|
|
|
### function_1(tableau1,tableau2)
|
|
> La complexité de cette fonction est de O(n*m) avec n la taille du premier tableau et m la taille du second
|
|
> puisque le second tableau est parcouru n fois.
|
|
|
|
### function_2(x)
|
|
> La complexité de cette fonction est de O(n) car x réduit de 1 à chaque itération jusqu'à atteindre 0.
|
|
|
|
### function_3(x)
|
|
> La complexité de cette fonction est de O(1) car il n'y a pas de boucle ni d'appel à d'autres fonctions.
|
|
|
|
## Exercice 3
|
|
|
|
> On a une boucle qui englobe toute la fonction<br>
|
|
> A l'interieur de cette boucle on a :
|
|
> - une boucle de complexité O(n)
|
|
> - un bubblesort de complexité O(n²)
|
|
> - une boucle contenant find_rank_student
|
|
>
|
|
> find_rank_student possède à la fois une boucle et un bubblesort, on a donc une complexité de O(n+n²) qu'on peut simplifier en O(n²)
|
|
> <br> On a donc une complexité de O(m * n + n² + n²) que l'on peut simplifier en O(m * n²)
|
|
|
|
## Exercice 4
|
|
|
|
> Mon algorithme de tri est composé de deux bubblesort avec une complexité de O(N²) chacun
|
|
> <br> Pour le premier bubblesort, il y a la fonction sum() utilisée, possédant une complexité de O(M)
|
|
> <br> L'algorithme est donc de complexité O(M*N²) |