TD4 - DEV5.1 Qualité algorithmique

Exo 2

function_1()

pire des cas de parcours nombre1*nombre2, donc complexité = O(nombre1*nombre2)

function_2()

Boucle parcourue jusqua que x = 0 donc il ya a x parcours de la boucle, complexité = O(x)

function_3()

un seul parcour de la boucle, complexité = O(1)

Exo 3

sort_students()

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);
    }
}

Si l'on suppose que:

La complexité de “malloc” est O(1)
La complexité de “free” est O(1)

On commence par calculer les complexité algorythmique des fonctions comprises dans sort_students().

D'abord la complexité de bublesort() :

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);
}

La boucle while continue tant que swapped = 1, or celle si ne l'est que lorsqu'il a parcourue entierement la boucle sans l'avoir modifier. Dans le meilleur des cas c'est 1 seul parcours, dans le pire c'est n² car il doit reinverser tout le tableau. Donc O = n².

Ainsi que de find_rank_student():

int <find_rank_student>(int student_grade, int* grades_array, int students_number)
{
    int position = -1;
    int i = 0;
    bubblesort(grades_array,students_number);
    for(i = students_number-1; i >= 0; i--)
    {
        if(grades_array[i] == student_grade)
        {
                position = students_number-i;
            break;
        }
    }
    return position;
}

Cette fonction contient bubblesort() qui a une complexité de N². De plus elle contien une boucle for qui s'execute students_number-1 fois. Dans le pire des cas cette fonction la boucle fera donc n-1 parcours. La complexité algorythmique est donc de O(n²+(n-1)).

On peut donc enfin calculer la complexité de sort_students():

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);
    }
}

Il y a trois boucle dans sort_students, l'une avec un malloc de complexité O(1) qui s'éxecute grades_number fois, un bublesort qui depend de students_number et deux autre boucles qui séxecute students_number fois. La premiere boucle sexecute donc n fois, le bublesort a une complexité de N², la seconde boubcle contient find_rank_student(), elle a donc une complexité de N*(N²+(N-1)) et enfin il y a un free qui vaut donc 1. Si l'on calcule cela fait donc = M(1+N+N²+N*(N²+(N-1))+1) = M(2+N+N²+N3+N²-N) = M(N3+2N²+2) On garde la plus complexité la plus elevé donc O(M*N3)

Exo 4

Mon code se compose en fait de 2 buble sort, la complexité de sort_bubble_array() donc de O(n²), et celle de bublesort_multi_array() est de O(n²+n²) donc O(n²)

3.7 KiB Raw Permalink Blame History