TD4_DEV51_Qualite_Algo

par SCHIED Killian

Exercice 2

Fonction 1

La complexité algorithmique de la fonction 1 est de O(n*m) dans le pire des cas (si on explore l'intégralité des 2 tableaux) ou de O(n+m) dans le meilleur des cas (si les 2 tableaux contiennent une liste qu'avec la même valeur (par exemple un tableau qui contient que des 1)).

Fonction 2

La complexité algorithmique de la fonction 2 est de O(x) dans le pire des cas (si le nombre est positif, il va le décrémenter de 1 jusqu'à qu'il soit égal à 0) ou de O(1) dans le meilleur des cas (si le nombre et négatif, il va retourner directement la valeur).

Fonction 3

La complexité algorithmique de la fonction 3 est de O(1) car il change valeur si x est supérieur, égal ou inférieur à 0 puis il retourne la valeur.

Exercice 3

La complexité algorithmique de la fonction "sort_students" est de : O(n*(m^3)).

// O(n*(m^3)) (on garde seulement m^3 et les autres s'annulent)
void sort_students(int** students_rank, int** students_array, int students_number, int grades_number)
{
    int i = 0, j = 0;
	// O(n)
    for(i = 0; i < grades_number; i++)
    {
        int * grades = (int*) malloc(students_number*sizeof(int)); // O(1)
		// O(m)
		for(j = 0; j < students_number; j++)
		{
			grades[j] = students_array[j][i];
		}
   		bubblesort(grades,students_number); // O(m^2)
		// O(m*m^2) <=> O(m^3)
		for(j = 0; j < students_number; j++)
		{
			students_rank[j][i] = find_rank_student(students_array[j][i],grades,students_number); // O(m^2)
		}
		free(grades); // O(1)
    }
}

// O(n^2)
void bubblesort(int* array, int length)
{
	int swapped, i, tmp;
	do
	{
		swapped = 0;
		for(i=1;i<length;i++)
		{
			if(array[i-1] > array[i])
			{
				tmp = array[i-1];
				array[i-1] = array[i];
				array[i] = tmp;
				swapped++;
			}
		}
	} while(swapped==1);
}

// O(n^2) (car O(n) s'annule)
int find_rank_student(int student_grade, int* grades_array, int students_number)
{
    int position = -1;
    int i = 0;
    bubblesort(grades_array,students_number); // O(n^2)
	// O(n)
    for(i = students_number-1; i >= 0; i--)
    {
        if(grades_array[i] == student_grade)
		{
			position = students_number-i;
			break;
		}
    }
    return position;
}

Exercice 4

La complexité algorithmique de l'algorithme dans sort_algorithm.py est de O(n^2 + 2*m).