Complexité polynomiale ?

Bonjour,

J'aimerai connaitre la complexité de "fonction". Je pense à une complexité polynomiale de degré 3 mais je n'en suis pas convaincu.

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34

void inverser(int a, int b, int *t) { for(int i=0;i<((b-a)/2)+1;i++) { int tmp=t[b-i]; t[b-i]=t[a+i]; t[a+i]=tmp; } }   bool test() { return ... ; }   void fonction(int **mat, int nb, sol s) { deb: for(int i=0;i<nb-2;i++) { for(int j=i+2;j<nb-1;j++)   if test( ) { inverser(i+1,j,s->tab); goto deb; } if test( ) { inverser(i+1, nb-1,s->tab); goto deb; } } }

---

Merci d'avance pour tout aide.

Citation:

---

Envoyé par kimikou

Bonjour,

J'aimerai connaitre la complexité de "fonction". Je pense à une complexité polynomiale de degré 3 mais je n'en suis pas convaincu.

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34

void inverser(int a, int b, int *t) { for(int i=0;i<((b-a)/2)+1;i++) { int tmp=t[b-i]; t[b-i]=t[a+i]; t[a+i]=tmp; } }   bool test() { return ... ; }   void fonction(int **mat, int nb, sol s) { deb: for(int i=0;i<nb-2;i++) { for(int j=i+2;j<nb-1;j++)   if test( ) { inverser(i+1,j,s->tab); goto deb; } if test( ) { inverser(i+1, nb-1,s->tab); goto deb; } } }

---

Merci d'avance pour tout aide.

---

Salut

Personnellement, comme tu fais une boucle de n dans une boucle de n et que tu appelles "inverser()" qui fait lui-aussi une boucle de n, je dirais aussi que c'est de complexité n3.
Ce qui me semble d'ailleurs étonnant. Même le tri à bulle qui est le plus lourd des tris n'est que de complexité n². Qu'est donc sensé faire cet algo ???