Discussion :

[Delnir]

Bonsoir,

je bloque sur un énoncé, pouvez-vous me débloquer.

1er exo:
Soit A et B 2 tableaux de taille n et contenant des entiers positifs.
Donner un algorithme (le plus éfficace possible) qui vérifie si A et B sont disjoints (c'est à dire ne contenant aucun élément en commun) Evaluer sa compléxité?

voilà ce que j'ai fait:
(je tri les 2 tableaux avec un tri fusion et ensuite je fait une fonction disjoint en O(n) pour dire si les tableaux sont disjoint ou non)

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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
 
void fusion(int *tab,int debut,int milieu,int fin){
  int tab1[milieu],tab2[fin-milieu],tailleTab2=fin-milieu,posA=0,posB=0,i;
  for(i=0;i<milieu;i++)
    tab1[i]=tab[i];
 
  for(i=0;i<tailleTab2;i++)
    tab2[i]=tab[milieu+i];
 
  for(i=0;(posA<milieu && posB<tailleTab2);i++){
    if(tab1[posA]>tab2[posB])
      tab[i]=tab2[posB++];
    else
      tab[i]=tab1[posA++];
  }
  for(;posA<milieu;)
    tab[i++]=tab1[posA++];
 
  for(;posB<tailleTab2;)
    tab[i++]=tab2[posB++]; 
}
 
void triFusion(int *tab,int debut,int fin){
  int milieu;
  if(debut<fin){
    milieu=(debut+fin)/2;
    triFusion(tab,debut,milieu);
    triFusion(tab,milieu+1,fin);
    fusion(tab,debut,milieu,fin);
  }
}
 
int disjoint(int *tab1,int *tab2,int n){
  int posA=0,posB=0,save,NTab;
  triFusion(tab1,1,n);
  triFusion(tab2,1,n);
 
  for(;(posA<n && posB<n);){
    if(tab1[posA]>tab2[posB]){
      if((posB || posA) && (tab2[posB]==save) && NTab==1)
	return 0;
      save=tab2[posB++];
      NTab=2;
    }
    else{
      if((posB || posA) && (tab1[posA]==save) && NTab==2)
	return 0;
      NTab=1;
      save=tab1[posA++];
    }
  }
  return 1;
}

je sais que le tri fusion est en O(n log n) et ma fonction disjoint en O(n)
donc logiquement je serai au final en O(n) si n<10 et O(n log n) si n >=10.

est ce bon?

je doit démontrer cette compléxité mais je n'arrive pas à calculer la compléxité du tri fusion, pouvez-vous m'expliquer comment faire?
(je comprend pas comment arrivé à n log n, je suis pas très bon en math )

2 iéme exo:

Soit A un tableau de n nombres réels positifs et distincts. Supposons que la différence enetre deux nombres quelconques dans A est au moins (1/10^5) et au plus (10^5). Proposer un algorithme en 0(n) pour trier le tableau A.

je trouve pas d'algorithme en 0(n), le seul algo que je trouve qui se raproche est en O(n+MAX), en cherchant le max et un tableau temporaire de taille MAX+1 et après je joue avec les indices du tableau pour trier.

je trouve pas, comment doit je m'y prendre?

merci d'avance pour votre aide.

[Pouet_forever]

Ton tri fusion est incorrect.

Pour faire ton premier exo tu n'as même pas besoin de trier ton tableau, il suffit tout simplement de tester toutes les valeurs une à une.
Tu prends la première valeur du premier tableau et tu la compare à toutes les valeurs du deuxième tableau. Tu prends la deuxième valeur du premier tableau et tu la compare à toutes les valeurs du deuxième tableau.
Etc.

O(n+MAX) == O(n)

[Delnir]

bizare chez moi sa marche sur tous les tests:

le code entier d'un tri fusion:

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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
 
#include <stdlib.h>
#include <stdio.h>
 
#define MAX 5
 
void affiche(int *tab){
  int i;
  for(i=0;i<MAX;i++)
    printf("%d ",tab[i]);
}
 
void fusion(int *tab,int debut,int milieu,int fin){
  int tab1[milieu],tab2[fin-milieu],i,posT1=0,posT2=0,tailleTab2=fin-milieu;
 
  for(i=0;i<milieu;i++)
     tab1[i]=tab[i];
 
  for(i=0;i<tailleTab2;i++)
     tab2[i]=tab[milieu+i];
 
  for(i=0;(posT1<milieu && posT2<tailleTab2);i++){
    if(tab1[posT1]>tab2[posT2])
      tab[i]=tab2[posT2++];
    else
      tab[i]=tab1[posT1++];
  }
 
  for(;posT1<milieu;posT1++,i++)
    tab[i]=tab1[posT1];
 
  for(;posT2<tailleTab2;posT2++,i++)
    tab[i]=tab2[posT2];
}
 
void triFusion(int *tab,int debut,int fin){
  int i,milieu;
  if(debut<fin){
    milieu=((fin+debut)/2);
    triFusion(tab,debut,milieu);
    triFusion(tab,milieu+1,fin);
    fusion(tab,debut,milieu,fin);
  }
}
 
int main(void){
  int tab[]={1,0,2,-1,3};
  printf("Avant trie:\n");
  affiche(tab);
  printf("\n");
  triFusion(tab,1,MAX);
  printf("Apres trie:\n");
  affiche(tab);
  printf("\n");
  return 0;
}

ensuite c'est un exercice d'algorithmique, qui demande l'algo plus éfficace possible !

O(nlog n) est plus éfficace qu'un algo en O(n^2) (ton exemple).

enfin sa O(n+MAX) == O(n), je suis pas vraiment d'accord, car tous dépend du tableau à trier!

tab[]={1,100000} n=2 et la je trouve qu'il est important de préciser O(n+MAX)

[Pouet_forever]

Essaye avec un autre tableau et tu verras que ton code ne retourne pas les résultats attendus :

Code :

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

1
2
3
4
5
6
/* Pour int tab[MAX]={0,1,2,3,4,5}; */
 
Avant trie:
0 1 2 3 4 5 0 0 0 
Apres trie:
0 0 0 1 2 3 4 5 0

La notion de complexité est un état 'général' des choses. Une complexité en O(n+3n+n+100n) sera égal à O(n) (quelque-soit le coefficient).

C'est vrai que mon exemple est en O(n^2), mais tu peux facilement améliorer en fusionnant les 2 tableaux, et en regardant les éléments en double (voire plus). Grossomodo c'est un tri fusion sur 2 tableaux, et en retourne 1 seul. Tu auras une complexité en O(n log(n))