Bonjour, voici l'énoncé de mon exercice, je dois déterminer le role, les opérations significatives puis le meilleur et pire cas.
je ne suis pas sur des résultats mais pour moi, le rôle est de supprimer tout les doublons x dans un vecteur. les opérations significatives sont v(i) mod x = 0, v(d) = v(j) et v(i) => x. le meilleur cas est lorsque que v(1) > x car l'algorithme s'arrête on a une comparaison et zéro affectation et le pire cas est lorsque notre vecteur est composé que de multiple de x et que x soit le dernier élement du vecteur, on a 2n comparaison + n affectation
Merci pour votre aide
- Edité par JorjeAmbino 11 novembre 2020 à 18:31:09
Le rôle est plus précis que ça: On remarque que la boucle "tant que" s’arrête soit à la fin du vecteur (i<=m) soit après avoir traité le dernier élément supérieur ou égal à x (car c'est une relation de supériorité dans un vecteur rangé par ordre décroissant). De plus pour chaque élément traité, si x divise cet élément, tu décale touts les éléments de ton vecteur et supprime l'actuel, en décrémentant de 1 l'indice final de la boucle.
On peut donc conclure en disant que cet algorithme supprime toute occurrence de x et de ses multiples du vecteur. La condition V(i) ne sert que d'optimisation car, si le vecteur est trié en ordre décroissant il n'y a pas d'occurrence de x ou de k*x (k entier supérieur à 1) après le dernier x d'une série.
Pour les opérations significatives, j'aurais répondu la même chose.
Pareil pour le meilleur cas. Mais pour le pire cas, on peut faire plus simple en disant juste que le vecteur V n'est composé que de x. Cela reviens au même mais c'est plus simple à construire et c'est souvent mieux, quand plusieurs cas sont de complexité équivalente, de donner le plus simple.
Le rôle est plus précis que ça: On remarque que la boucle "tant que" s’arrête soit à la fin du vecteur (i<=m) soit après avoir traité le dernier élément supérieur ou égal à x (car c'est une relation de supériorité dans un vecteur rangé par ordre décroissant). De plus pour chaque élément traité, si x divise cet élément, tu décale touts les éléments de ton vecteur et supprime l'actuel, en décrémentant de 1 l'indice final de la boucle.
On peut donc conclure en disant que cet algorithme supprime toute occurrence de x et de ses multiples du vecteur. La condition V(i) ne sert que d'optimisation car, si le vecteur est trié en ordre décroissant il n'y a pas d'occurrence de x ou de k*x (k entier supérieur à 1) après le dernier x d'une série.
Pour les opérations significatives, j'aurais répondu la même chose.
Pareil pour le meilleur cas. Mais pour le pire cas, on peut faire plus simple en disant juste que le vecteur V n'est composé que de x. Cela reviens au même mais c'est plus simple à construire et c'est souvent mieux, quand plusieurs cas sont de complexité équivalente, de donner le plus simple.
Au plaisir.
J'ai remarqué un problème dans le pire cas je pense ,lors d'une itération, nous aurons 2 comparaison et à cause de la boucle pour nous avons (n-1) affectation car pour j= i --> m-1 faire
v(j) <- v(j+1)
m <- m-1
du coup la complexité en affectation serait plutot de la suite des (n-1) vu que cela décrémente non ?
- Edité par JorjeAmbino 10 novembre 2020 à 20:02:06
Oui c'est vrai, mais je vois pas le problème. Quand on demande le pire des cas, on demande une forme, pas une taille. En l'occurrence la pire forme, on a trouvé que c'était un tableau qui ne contient que des multiples de x.
La complexité s'exprime quasiment toujours en fonction du nombre d'entrée, et c'est normal. Mais ce qu'on appelle le "pire cas", n'a pas de rapport direct avec la complexité. Si c'était le cas, la "pire valeur" n'existerait que dans très rares algorithmes.
Petite démo pour le fun:
On suppose que la taille influe sur le pire cas.
Soit Vp, le pire vecteur, de taille n. On définit Vp' de taille n+1, tq Vp'(x) = Vp(x) pour tout x, et Vp'(n+1) = Vp(n).
Or taille de Vp' > taille de Vp, donc Vp' pire que Vp. Or, par hypothèse, Vp est le pire vecteur mais Vp != Vp' !!!!!
Absurde.
Donc la taille de l'entrée n'influe pas sur le pire cas
"Si ce n'est pas dur, ce n'est pas intéressant"
"Si ce n'est pas dur, ce n'est pas intéressant"
"Si ce n'est pas dur, ce n'est pas intéressant"
"Si ce n'est pas dur, ce n'est pas intéressant"