Ex2 - Calculs de complexité de fonctions

Complexité algorithmique :

• fonction_1 : O(n*m)
  Cette fonction contient des boucles imbriquées. Dans le pire des cas, il faudra parcourir n x m.
• fonction_2 : O(n)
  La boucle while s'exécute au maximum n fois.
• fonction_3 : O(1)
  Cette fonction ne contient pas de boucle. Chaque condition est évaluée une seule fois, indépendamment de la taille des données d'entrée.

Ex3 - student_rank.c

void sort_students(int** students_rank, int** students_array, int students_number, int grades_number)
{
    int i = 0, j = 0;
    for(i = 0; i < grades_number; i++)
    {
        int * grades = (int*) malloc(students_number*sizeof(int));
	for(j = 0; j < students_number; j++)
	{
	    grades[j] = students_array[j][i];
	}
        bubblesort(grades,students_number);
	for(j = 0; j < students_number; j++)
	{
            students_rank[j][i] = find_rank_student(students_array[j][i],grades,students_number);
	}
	free(grades);
    }
}

1. La boucle externe s'exécute m fois, où m représente grades_number La complexité est donc O(m).
2. La copie des notes prend O(n),où n est le nombre d'étudiants.
3. Le tri bublesort a une complexité de O(n²)
4. find_rank_student la complexité de cette étape est dominée par le tri des étudiants bubblesort donc O(n²).

À chaque itération (pour chaque groupe de notes m), les opérations dominantes sont le tri des n étudiants avec une complexité de O(n²) ainsi la complexité totale est O(m*n²).

Ex4 - Algorithme de tri

1. Tri des sous-listes :

Si une sous-liste a une taille de m, la complexité du tri de cette sous-liste est O(m²) car l'algorithme de tri parcourt la sous-liste m et, à chaque fois, il effectue m-1 comparaisons. il y a n sous-listes au total. Donc, la complexité totale du tri des sous-listes est O(n*m²).

2. Tri liste principale

À chaque itération, nous comparons les sommes des sous-listes. Calculer la somme des éléments d'une sous-liste prend O(m) temps (car la somme des m éléments de la sous-liste doit être calculée). Donc, pour chaque comparaison, la complexité est O(m) (pour calculer la somme), et il y a O(n²) comparaisons au total dans le tri à bulle de la liste principale. La complexité du tri de la liste principale est donc O(n²*m)

Donc, la complexité totale est O( n*m² + n²*m )