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.