Discussion :

[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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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.

[Sve@r]

Bonjour,

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

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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 ???