algo de tri & compléxité

Version imprimable

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:

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.

03/02/2010, 22h55
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) :aie:

bizare chez moi sa marche sur tous les tests:

le code entier d'un tri fusion:

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
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) :D

04/02/2010, 19h56
Pouet_forever
Essaye avec un autre tableau et tu verras que ton code ne retourne pas les résultats attendus :
Code:

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)) ;)