Fusion de Tri du Temps et de l'Espace de la Complexité

MergeSort temps la Complexité est O(nlgn) qui est un des fondamentaux de la connaissance.
Fusion de Tri de la complexité de l'espace sera toujours en O(n), y compris avec des tableaux.
Si vous dessinez l'espace arbre, il semble que, même si l'espace de la complexité est O(nlgn). Cependant, comme le code est un parcours en Profondeur d'Abord le code, il vous sera toujours seulement être en expansion le long d'une branche de l'arbre, par conséquent, le total de l'utilisation de l'espace requis sera toujours borné par O(3n) = O(n).

Par exemple, si vous dessinez à l'espace de l'arbre, il me semble qu'il est O(nlgn)

                             16                                 | 16
                            / \                              
                           /   \
                          /     \
                         /       \
                        8          8                            | 16
                       /\        /\
                      /  \      /  \
                     4     4    4     4                         | 16
                    /\   /\  /\   /\
                   2   2 2   2.....................             | 16
                  /\  /\ ........................
                 1  1  1 1 1 1 1 1 1 1 1 1 1 1 1 1              | 16

où la hauteur de l'arbre est en O(logn) => Espace complexité est en O(nlogn) + n) = O(nlogn).
Cependant, ce n'est pas le cas dans le code comme il ne les exécute pas en parallèle. Par exemple, dans le cas où N = 16, c'est la façon dont le code pour mergesort exécute. N = 16.

                           16
                          /
                         8
                        /
                       4
                     /
                    2
                   /\
                  1   1

remarquez comment le numéro de l'espace utilisé est de 32 = 2n = 2*16 < 3n

Puis il fusionner vers le haut

                           16
                          /
                         8
                        /
                       4
                     / \
                    2    2
                        /\                
                       1   1

ce qui est de 34 < 3n.
Puis il fusionner vers le haut

                           16
                          /
                         8
                        /\
                       4   4
                          /
                         2
                        /\ 
                       1   1

36 < 16 * 3 = 48

puis il fusionner vers le haut

                           16
                          /\
                         8  8
                           /\
                          4   4
                             /\
                            2   2
                                /\
                               1  1

16 + 16 + 14 = 46 < 3*n = 48

dans un plus grand cas, n = 64

                     64
                    / \
                   32  32
                       /\
                      16  16
                          /\
                         8  8
                           /\
                          4   4
                             /\
                            2   2
                                /\
                               1  1

qui est de 64*3 <= 3*n = 3*64

Vous pouvez le prouver par induction pour le cas général.

Par conséquent, l'espace de la complexité est toujours borné par O(3n) = O(n), même si vous mettez en œuvre avec des tableaux aussi longtemps que vous le nettoyage de l'espace utilisé après la fusion et de ne pas exécuter du code en parallèle, mais de manière successive.

Exemple de mon application est donnée ci-dessous:

templace<class X> 
void mergesort(X a[], int n) //X is a type using templates
{
    if (n==1)
    {
        return;
    }
    int q, p;
    q = n/2;
    p = n/2;
    //if(n % 2 == 1) p++; //increment by 1
    if(n & 0x1) p++; //increment by 1
        //note: doing and operator is much faster in hardware than calculating the mod (%)
    X b[q];

    int i = 0;
    for (i = 0; i < q; i++)
    {
        b[i] = a[i];
    }
    mergesort(b, i);
    //do mergesort here to save space
    //http://stackoverflow.com/questions/10342890/merge-sort-time-and-space-complexity/28641693#28641693
    //After returning from previous mergesort only do you create the next array.
    X c[p];
    int k = 0;
    for (int j = q; j < n; j++)
    {
        c[k] = a[j];
        k++;
    }
    mergesort(c, k);
    int r, s, t;
    t = 0; r = 0; s = 0;
    while( (r!= q) && (s != p))
    {
        if (b[r] <= c[s])
        {
            a[t] = b[r];
            r++;
        }
        else
        {
            a[t] = c[s];
            s++;
        }
        t++;
    }
    if (r==q)
    {
        while(s!=p)
        {
            a[t] = c[s];
            s++;
            t++;
        }
    }
    else
    {
        while(r != q)
        {
            a[t] = b[r];
            r++;
            t++;
        }
    }
    return;
}

Espérons que cette aide!=)

Bientôt Chee Loong,

De l'université de Toronto

Pire des cas, la performance de la fusion de tri : O(n log n),
Dans le meilleur des cas les performances de la fusion de tri : O(n log n) typiquement, O(n) variante naturelle,
La moyenne des performances de fusion tri : O(n log n),
Pire-cas de l'espace de la complexité de la fusion de tri : О(n) total O(n) auxiliaire