la complexité d'une fonction qui enlève les elements redondants dans une liste chainée

bonjour à Tous,

pouvez vous m'aidez SVP à calculer la compléxité de la fonction suivante:

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23

liste redondance(liste l){ liste red,p,prev; if(l==NULL) return l; red=l; while(red!=NULL){ p=red->suivant; prev=red; while(p!=NULL){ if(p->val==red->val){ prev->suivant=p->suivant; free(p); p=prev->suivant; } else{ p=p->suivant; prev=prev->suivant; } } red=red->suivant; } return(l); }

---

ma réponse est o(n²)=o(n*n), o(n) est le nombre d'itérations de la première boucle "while" et O(n) c'est la deuxieme grandeur de la deuxieme boucle "while". et vu l'imbrication, j'ai multiplié n par n.

vos avis please, sinon pouvez vous me dire comment je peux calculer la complexité de telle function?

merci d'avance

Oui :mrgreen: mais non :zoubi:

C'est bien O(n²)

Mais tu parcours ta liste en entier (2ième while) mais ton 1ier while avance toujours de 1.
Donc, à 1 près, (n - 1) + (n - 2) + ... + 2 + 1 = (n * (n - 1)) / 2
On avance de 1 à chaque tour de boucle, parce qu'on a déjà testé la valeur et on ne veut pas rester bloqué :whistle:

merci Foetus pour votre réponse. je voudrais bien comprendre d'ou vient (n * (n - 1)) / 2, peut etre parceque le nombre d'itérations de la deuxieme boucle est bien une suite arithmétique?

Mise en explication : :mrgreen: Tu prends la liste [1, 2, 3, 4, 5], 5 éléments

Étape 1 :
Tu commence à 1, qui n'est pas NULL. Tu vas le tester avec 2, 3, 4, 5 -> 4 opérations
Étape 2 :
Tu prends le suivant (ligne 20), donc 2, qui n'est pas NULL. Tu vas le tester avec 3, 4, 5 -> 3 opérations
Étape 3 :
Tu prends le suivant (ligne 20), donc 3, qui n'est pas NULL. Tu vas le tester avec 4, 5 -> 2 opérations
Étape 4 :
Tu prends le suivant (ligne 20), donc 4, qui n'est pas NULL. Tu vas le tester avec 5 -> 1 opération
Étape 5 :
Tu prends le suivant (ligne 20), donc 5, qui n'est pas NULL. Tu vas le tester avec rien (ligne 9, tu ne rentres pas dans la 2ième boucle while)
Étape 6 :
Tu prends le suivant (ligne 20), donc NULL. Ligne 6, tu sors de la 1iere boucle while.


Donc c'est bien :mrgreen: [(n - 1) + (n - 2) + ... + 2 + 1] opérations
Et j'ai regardé wiki :oops: pour sortir (n * (n - 1)) / 2 -> (5 * 4) / 2 = 10 opérations


Après c'est un maximum, parce que ta liste peut diminuer de taille - les éléments redondants vont être retirés/ détruits :zoubi:

Bonjour

Citation:

---

Envoyé par thouraya24

merci Foetus pour votre réponse. je voudrais bien comprendre d'ou vient (n * (n - 1)) / 2, peut etre parceque le nombre d'itérations de la deuxieme boucle est bien une suite arithmétique?

---

C'est même la toute première des suites arithmétiques U0=0 et Un+1=Un + 1
La somme des n premiers termes est alors donné par la formule Sn=n * (n-1) /2. C'est aussi le nombre de "tchin" quand n personnes trinquent ensembles 2 à 2.

Et si la suite commence à 1, alors la formule devient Sn=n * (n+1) / 2.

merci beaucoup Sve@r, je pense que pour la démontrer, il faut utiliser la notation mathématique

somme pour i=1 à N (certain nombres dinstructions) * somme pour j allant de i+1 à N (d'un certain nombre d'instructions)

Citation:

---

Envoyé par foetus

Mise en explication : :mrgreen: Tu prends la liste [1, 2, 3, 4, 5], 5 éléments

Étape 1 :
Tu commence à 1, qui n'est pas NULL. Tu vas le tester avec 2, 3, 4, 5 -> 4 opérations
Étape 2 :
Tu prends le suivant (ligne 20), donc 2, qui n'est pas NULL. Tu vas le tester avec 3, 4, 5 -> 3 opérations
Étape 3 :
Tu prends le suivant (ligne 20), donc 3, qui n'est pas NULL. Tu vas le tester avec 4, 5 -> 2 opérations
Étape 4 :
Tu prends le suivant (ligne 20), donc 4, qui n'est pas NULL. Tu vas le tester avec 5 -> 1 opération
Étape 5 :
Tu prends le suivant (ligne 20), donc 5, qui n'est pas NULL. Tu vas le tester avec rien (ligne 9, tu ne rentres pas dans la 2ième boucle while)
Étape 6 :
Tu prends le suivant (ligne 20), donc NULL. Ligne 6, tu sors de la 1iere boucle while.


Donc c'est bien :mrgreen: [(n - 1) + (n - 2) + ... + 2 + 1] opérations
Et j'ai regardé wiki :oops: pour sortir (n * (n - 1)) / 2 -> (5 * 4) / 2 = 10 opérations


Après c'est un maximum, parce que ta liste peut diminuer de taille - les éléments redondants vont être retirés/ détruits :zoubi:

---

merci bcp Foetus, très utile votre réponse.
il me reste une question svp, si je voudrais savoir la complexité du "if" qu'on trouve dans le "while", ça sera combien SVP?

Code:

---

1 2 3 4 5 6 7 8 9

if(p->val==red->val){ prev->suivant=p->suivant; free(p); p=prev->suivant; } else{ p=p->suivant; prev=prev->suivant; }

---

et en particulier la complexité de cette instruction:

Code:

---

prev->suivant=p->suivant;

---

merci encore une fois :mrgreen:

Citation:

---

Envoyé par thouraya24

la complexité du "if" qu'on trouve dans le "while", ça sera combien SVP?
... et en particulier la complexité de cette instruction

---

Il faut savoir qu'il existe plusieurs compléxités : algorithme, espace, temps [, ...]

Et le truc qui semble "bizarre" avec la compléxité algorithme, c'est que toutes les opérations basiques c'est O(1) :mrgreen: - ce qui comprend les tests, les affectations, les opérations mathématique et logiques, ...
Et que quelque soit le nombre d'opérations basiques dans un bloc, cela fera toujours O(1) (exemple absurde : :fou: 1 fonction avec 1 milliard d'affectations c'est O(1))

merci Foetus pour votre réponse, la complexité de la structure conditionnelle est certainement une constante mais je pense pas que c'est de l'ordre de 1, un exemple, dans le code ci dessous, la complexité est T(n)=3

Code:

---

1 2 3 4 5 6

def puissanceMoinsUn(n): if n%2==0: res = 1 else: res = -1 return res

---

explication de l'auteur: Le test de la conditionnelle comporte une opération arithmétique et une comparaison.

Chaque alternative possède une affectation, ainsi le maximum des coûts des différentes alternatives est de un. on a donc T(n)=3.

Citation:

---

Envoyé par thouraya24

explication de l'auteur: Le test de la conditionnelle comporte une opération arithmétique et une comparaison.

Chaque alternative possède une affectation, ainsi le maximum des coûts des différentes alternatives est de un. on a donc T(n)=3.

---

Justement, si je ne dis pas de bêtises :oops:, nous ne sommes plus avec une compléxité algorithme mais plus une compléxité opérations/ temps (???)

Donc on a

• compléxité algorithme : O(1)
• compléxité opérations/ temps : 1 affectation, 1 test et 1 opération mathématique, soit 3 * O(1)/ 3 opérations (<- je ne sais pas trop comment on le dit)

Citation:

---

Envoyé par thouraya24

merci Foetus pour votre réponse, la complexité de la structure conditionnelle est certainement une constante mais je pense pas que c'est de l'ordre de 1, un exemple, dans le code ci dessous, la complexité est T(n)=3

Code:

---

1 2 3 4 5 6

def puissanceMoinsUn(n): if n%2==0: res = 1 else: res = -1 return res

---

explication de l'auteur: Le test de la conditionnelle comporte une opération arithmétique et une comparaison.

Chaque alternative possède une affectation, ainsi le maximum des coûts des différentes alternatives est de un. on a donc T(n)=3.

---

La complexité d'un algorithme ne se mesure pas en fonction du nombre d'éléments à traiter (que le tableau ait 10 ou 10 milliards ça change rien); ni en fonction des instructions inscrites dans ce traitement ; mais en fonction du nombre de répétitions de ce traitement des éléments.
Si un tableau de N éléments est traité M fois (exemple d'un tri de base), on dit alors que la complexité est en N² (même si M n'est pas tout à fait égal à N, c'est juste pour donner un ordre d'idée). Si le tableau n'est traité qu'une fois (par exemple on veut additionner ses éléments) alors sa complexité est en N(1). Et si le tableau est traité un nombre de fois ne dépassant pas la moitié de ses éléments (comme par exemple un qsort appliqué sur un tableau uniformément distribué) alors on parle de N * log(N).
Mais le traitement en lui-même (s'il contient un ou deux "if", une affectation, un calcul, etc) n'entre pas en ligne de compte. On considère que le traitement est nécessaire et que tel qu'il est écrit il est le meilleur qui soit même si on l'écrit différemment (par exemple: res=(n % 2) == 0 ?1 :-1 ou bien res=-2 * (n % 2) + 1).