1. #1
    Futur Membre du Club
    Homme Profil pro
    Étudiant
    Inscrit en
    novembre 2015
    Messages
    4
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : Maroc

    Informations professionnelles :
    Activité : Étudiant
    Secteur : Enseignement

    Informations forums :
    Inscription : novembre 2015
    Messages : 4
    Points : 5
    Points
    5

    Par défaut Tri fusion : complexité du découpage

    Salut,
    Je ne comprend pas pourquoi la partie découpage(uniquement) dans le tri de fusion a une complexité O(log(n)) et non pas O(n),
    par exemple si on veut trié un tableau de n=8 alors on doit faire 7 opérations de découpage :

    Nom : tf2.png
Affichages : 40
Taille : 26,5 Ko

    pour trié un tableau de 100 éléments on doit faire 100 opérations,ce qui doit normalement correspondre a O(n) non?

    dans le cas de l'algorithme de dichotomie on a aussi une complexité log(n) ce qui est compréhensible car pour trouvé un élément dans une liste trié on effectue k opérations avec n=2^k
    par exemple pour n=8 on peut trouvé l’élément dans max 3 opérations,par exemple trouvé la valeur 1 :

    Nom : dic2.png
Affichages : 37
Taille : 6,5 Ko

    pour un n=100 on effectue 6 opérations

    -alors voila pourquoi les 2 algorithmes on la mème complexité log(n) alors que dans le cas de l'algorithme de dichotomie on effectue uniquement k opérations pour trouvé l’élément alors que dans le cas du découpage du tri de fusion on effectue 2^k opérations?

    Toute aide est la bienvenu,Merci
    Images attachées Images attachées  

  2. #2
    Rédacteur
    Avatar de pseudocode
    Homme Profil pro
    Architecte système
    Inscrit en
    décembre 2006
    Messages
    10 027
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 44
    Localisation : France, Hérault (Languedoc Roussillon)

    Informations professionnelles :
    Activité : Architecte système
    Secteur : Industrie

    Informations forums :
    Inscription : décembre 2006
    Messages : 10 027
    Points : 15 578
    Points
    15 578

    Par défaut

    Citation Envoyé par fil1990 Voir le message
    Je ne comprend pas pourquoi la partie découpage(uniquement) dans le tri de fusion a une complexité O(log(n)) et non pas O(n),
    La partie "découpage" a une complexité nulle car il n'y a aucune opération réalisée (aucun traitement sur les données).
    D'ailleurs les 4 premières lignes de ton exemple montrent les mêmes données dans le même ordre, la seule différence étant l'espace entre les cases.

    Cette partie est utile seulement pour expliquer comment l'algorithme fonctionne. Pour être précis, elle explique qu'on va considérer les données comme les feuilles d'un arbre et pas comme une liste à accès séquentielle.

    Code C : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    int[8]          L = {   3 , 4  ,  6 , 2   ,   5 , 1  ,  8 , 7   }
    int[2][4]       L = {{  3 , 4  ,  6 , 2  },{  5 , 1  ,  8 , 7  }}
    int[2][2][2]    L = {{{ 3 , 4 },{ 6 , 2 }},{{ 5 , 1 },{ 8 , 7 }}}
    int[2][2][2][1] L = {{{{3},{4}},{{6},{2}}},{{{5},{1}},{{8},{7}}}}
    ALGORITHME (n.m.): Méthode complexe de résolution d'un problème simple.

  3. #3
    Rédacteur/Modérateur

    Avatar de yahiko
    Homme Profil pro
    Ninja
    Inscrit en
    juillet 2013
    Messages
    1 134
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Ninja

    Informations forums :
    Inscription : juillet 2013
    Messages : 1 134
    Points : 6 448
    Points
    6 448
    Billets dans le blog
    43

    Par défaut

    Ce que tu nommes le "découpage" a effectivement une complexité en O(n). Il faut lire tous les éléments pour les individualiser (phase de la descente de l'algo récursif). Cette opération n'a absolument aucun rapport avec la recherche dichotomique.
    Ce qui prend O(n.log(n)), c'est l'étape de fusion (phase de remontée de l'algo récursif).
    O(n + n.log(n) = O(n.log(n)).
    On néglige le plus petit terme, n, au profit du plus grand n.log(n). D'où la complexité finale du tri fusion en O(n.log(n)).
    Tutoriels et FAQ TypeScript

  4. #4
    Futur Membre du Club
    Homme Profil pro
    Étudiant
    Inscrit en
    novembre 2015
    Messages
    4
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : Maroc

    Informations professionnelles :
    Activité : Étudiant
    Secteur : Enseignement

    Informations forums :
    Inscription : novembre 2015
    Messages : 4
    Points : 5
    Points
    5

    Par défaut

    Citation Envoyé par yahiko Voir le message
    Ce que tu nommes le "découpage" a effectivement une complexité en O(n). Il faut lire tous les éléments pour les individualiser (phase de la descente de l'algo récursif). Cette opération n'a absolument aucun rapport avec la recherche dichotomique.
    Ce qui prend O(n.log(n)), c'est l'étape de fusion (phase de remontée de l'algo récursif).
    O(n + n.log(n) = O(n.log(n)).
    On néglige le plus petit terme, n, au profit du plus grand n.log(n). D'où la complexité finale du tri fusion en O(n.log(n)).
    Merci pour votre réponse,c'est ce que je pensait moi aussi,enfaîte ce qui ma perturbé c'est un cours en ligne,voici ce qu'il dit :

    "Quand est-ce que la phase de découpage s'arrête ? Quand on est arrivé à des tableaux de taille 1. Et combien de fois faut-il diviser N par 2 pour obtenir 1 ? On l'a déjà vu, c'est la fonction logarithme ! En effet, si on a un tableau de taille 1, on renvoie le tableau en une seule opération (f(0) = 1), et si on double la taille du tableau il faut faire une découpe de plus (f(2*N) = f(N) + 1). C'est bien notre sympathique fonction du chapitre précédent. On a donc log(N) phases de "découpe" successives."

  5. #5
    Rédacteur/Modérateur

    Avatar de yahiko
    Homme Profil pro
    Ninja
    Inscrit en
    juillet 2013
    Messages
    1 134
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Ninja

    Informations forums :
    Inscription : juillet 2013
    Messages : 1 134
    Points : 6 448
    Points
    6 448
    Billets dans le blog
    43

    Par défaut

    Moralité : ne pas croire sur parole tout ce qu'on trouve sur le net
    Tutoriels et FAQ TypeScript

  6. #6
    Rédacteur
    Avatar de pseudocode
    Homme Profil pro
    Architecte système
    Inscrit en
    décembre 2006
    Messages
    10 027
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 44
    Localisation : France, Hérault (Languedoc Roussillon)

    Informations professionnelles :
    Activité : Architecte système
    Secteur : Industrie

    Informations forums :
    Inscription : décembre 2006
    Messages : 10 027
    Points : 15 578
    Points
    15 578

    Par défaut

    Citation Envoyé par fil1990 Voir le message
    Merci pour votre réponse,c'est ce que je pensait moi aussi,enfaîte ce qui ma perturbé c'est un cours en ligne,voici ce qu'il dit :

    "Quand est-ce que la phase de découpage s'arrête ? Quand on est arrivé à des tableaux de taille 1. Et combien de fois faut-il diviser N par 2 pour obtenir 1 ? On l'a déjà vu, c'est la fonction logarithme ! En effet, si on a un tableau de taille 1, on renvoie le tableau en une seule opération (f(0) = 1), et si on double la taille du tableau il faut faire une découpe de plus (f(2*N) = f(N) + 1). C'est bien notre sympathique fonction du chapitre précédent. On a donc log(N) phases de "découpe" successives."
    Tu as log(N) phases de fusions successives (4 dernières lignes dans ton image). Chaque fusion nécessite de traiter les N éléments (= la totalité de la ligne).

    Plus formellement, la complexité pour trier une liste de taille n est égale à la complexité pour trier la demi-liste de gauche, plus la complexité pour trier la demi-liste de droite, plus la complexité pour fusionner les deux demi-listes:

    C(n) = C(n/2) + C(n/2) + n = 2*C(n/2) + n

    En partant d'une liste initiale de taille n=2^p, on trouve le terme général:

    C(n) = C(2^p) = 2*C(2^(p-1)) + n = 4*C(2^(p-2)) + 2*n = 8*C(2^(p-3)) + 3*n = ... = (2^p)*C(1) + p*n

    La complexité pour trier une liste d'un seul élément est de 0 (rien a faire): C(1)=0

    C(n) = (2^p)*0 + p*n = p*n =log2(n)*n --> O( n*log(n) )
    ALGORITHME (n.m.): Méthode complexe de résolution d'un problème simple.

  7. #7
    Futur Membre du Club
    Homme Profil pro
    Étudiant
    Inscrit en
    novembre 2015
    Messages
    4
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : Maroc

    Informations professionnelles :
    Activité : Étudiant
    Secteur : Enseignement

    Informations forums :
    Inscription : novembre 2015
    Messages : 4
    Points : 5
    Points
    5

    Par défaut

    Citation Envoyé par pseudocode Voir le message
    Tu as log(N) phases de fusions successives (4 dernières lignes dans ton image). Chaque fusion nécessite de traiter les N éléments (= la totalité de la ligne).
    J'ai 3 phases de fusion(2^3 = 8),chaque phase nécessite de traiter n éléments
    donc n*3 éléments a traiter,ce qui veut dire n*log(n)
    Sa devrait s'appliquer aussi dans la partie découpage non?,car chaque phase de découpage nécessite de parcourir le tableau et mettre ses valeurs dans les 2 tableaux(gauche,droite),
    par exemple dans la 1er phase on parcours le tableau initiale et on place ses valeurs dans les 2 tableaux crée,la 2eme phase on parcours les 2 tableaux (n/2)*2,et ainsi de suite....

    voila mon code :
    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
    		size_tab* tri_fusion(int tab[],int n)
    		{
    			size_tab* st=new size_tab[1];
    			st->taille=n;
    			if(n==1)
    			{
    				st->tab=tab;
    			}
    			else{
    				int mg=floor(n/2);
    				int md=n-mg;
    				int g[mg],d[md];
    				remplir(tab,g,0,mg); //remplie le tableau gauche
    				remplir(tab,d,mg,n);
    				size_tab* st_g=tri_fusion(g,mg);
    				size_tab* st_d=tri_fusion(d,md);
    				delete[] g;
    				delete[] d;
    				st->tab= fusion(st_g,st_d);
    				delete[] st_g;
    				delete[] st_d;
    			}
    			return st;
    		}

  8. #8
    Rédacteur
    Avatar de pseudocode
    Homme Profil pro
    Architecte système
    Inscrit en
    décembre 2006
    Messages
    10 027
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 44
    Localisation : France, Hérault (Languedoc Roussillon)

    Informations professionnelles :
    Activité : Architecte système
    Secteur : Industrie

    Informations forums :
    Inscription : décembre 2006
    Messages : 10 027
    Points : 15 578
    Points
    15 578

    Par défaut

    Techniquement parlant, tu n'as pas besoin de créer et remplir les sous-tableaux intermédiaires.
    Les appels récursifs peuvent se limiter à indiquer la portion du tableau original sur laquelle l'algo doit opérer.

    Seule l'étape de fusion nécessite un sous-tableau temporaire qui est alors recopié dans le tableau original.

    Code java : 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
    int[] tab= {3,4,6,2,5,1,8,7};
    mergesort(tab,0,8);
     
    void mergesort(int[] tab,int offset, int len) {
        if (len<=1) return;
     
        int halflen=len/2;
        mergesort(tab, offset, halflen);
        mergesort(tab, offset+halflen,len-halflen);
     
        int[] merged = new int[len]; 
        int i=offset, imax=offset+halflen, j=imax, jmax=offset+len, k=0;
        while(i<imax && j<jmax) merged[k++]=(tab[i]<=tab[j])?tab[i++]:tab[j++];
        while(i<imax) merged[k++]=tab[i++];
        while(j<jmax) merged[k++]=tab[j++];
     
        for(k=0;k<len;k++) tab[offset+k]=merged[k];
    }
    ALGORITHME (n.m.): Méthode complexe de résolution d'un problème simple.

+ Répondre à la discussion
Cette discussion est résolue.

Discussions similaires

  1. tri - fusion de fichiers
    Par Fabien92 dans le forum z/OS
    Réponses: 6
    Dernier message: 11/08/2009, 17h29
  2. Tri fusion avec pthread
    Par Sh4dow49 dans le forum Débuter
    Réponses: 34
    Dernier message: 22/06/2008, 21h02
  3. Complexité de l'algorithme de Tri Fusion
    Par judge06 dans le forum Général Algorithmique
    Réponses: 10
    Dernier message: 26/03/2007, 22h04
  4. le tri fusion ne tri pas.
    Par argon dans le forum Général Algorithmique
    Réponses: 11
    Dernier message: 27/06/2006, 23h08

Partager

Partager
  • Envoyer la discussion sur Viadeo
  • Envoyer la discussion sur Twitter
  • Envoyer la discussion sur Google
  • Envoyer la discussion sur Facebook
  • Envoyer la discussion sur Digg
  • Envoyer la discussion sur Delicious
  • Envoyer la discussion sur MySpace
  • Envoyer la discussion sur Yahoo