Compte-rendu du TD4 par William Gentil
Exercice 2
Fonction 1
La fonction 1 prend en arguments deux tableaux différents. On peut y voir une bouvle for à l'intérieur d'une autre boucle for : on peut donc penser que la compléxité serait de n², sauf que les deux tablaeux peuvent avoir des valeurs différentes donc on serait plutôt sur une compléxité de xn. On pourrait tout de même ajouter que dans la deuxième boucle for on à l'exécution d'une action avec un break si le nombre1=nombre2 ce qui veut dire que notre complexité xn est le cas le plus pessimiste mais il pourrait y avoir une compléxité de O(1) si on venait à trouver dès la première case des deux tableaux la même valeur.
Résultat : O(xn)
Fonction 2
La fonction 2 utilise une boucle while qui dit que tanyt que x est supérieur à 0, on ajoute x à valeur et on décrémente x de 1. Ce qui veut dire que la complexité est de O(x) car il faut que x=0 pour finir la boucle et x=0 seulement lorsque l'on arrive à x+(x*(-1)). Autrement dit, il faut que l'on décrémente x de x fois pour trouver la complexité maximale.
Résultat : O(n)
Fonction 3
La fonction 3 est triviale, on a une fonction qui prend x en argument et qui traite la valeur de valeur selon la position de x par rapport à 0. Maintenant, la complexité serait de O(1) car l'ordinateur vérifie tous les if et ne fera qu'une seule instance car si un if est notre cas alors les deux autres ne sont forcément pas notre cas.
Résultat : O(1)
Exercice 3
Le tri des tableaux passe par un premier calcul de la somme de toutes les valeurs pour tous les tableaux puis ensuite on les trie par ordre croissant selon la valeur de la somme de leurs valeurs. Le nombre de dimensions influe donc énormément sur le complexité car il multiplie le nombre de tableaux et d'éléments. On trouve donc une complexité normalement de O(m^n).