la complexité de l'espace de la matrice fusion utilisant le tri

voix
6

Cet algorithme est mergesort, je sais que cela peut être à la recherche bizarre pour vous, mais mon objectif principal est sur le calcul de la complexité de l'espace de cet algorithme.

Si nous regardons l'arbre de récurrence de la fonction mergesort et essayer de retracer l'algorithme alors la taille de la pile sera log(n). Mais puisque la mergefonction est là aussi à l' intérieur du mergesortqui crée deux tableaux de taille n/2, n/2puis - je trouver d' abord devrait la complexité de l' espace de la relation de récurrence et, dois - je ajouter que n/2 + n/2cela deviendra O(log(n) + n).

Je connais la réponse, mais je suis confus dans le processus. Quelqu'un peut-il me dire la procédure correcte?

Cette confusion est due à la fusion fonction non récurrente, mais appelé dans une fonction récursive

Et pourquoi nous disons que la complexité de l' espace sera O(log(n) + n)et par la définition de la complexité de l' espace de fonction récursive, on calcule généralement la hauteur de l' arbre récursif

Merge(Leftarray, Rightarray, Array) {
    nL <- length(Leftarray)
    nR <- length(Rightarray)
    i <- j <- k <- 0
    while (i < nL && j < nR) {
        if (Leftarray[i] <= Rightarray[j])
            Array[k++] <- Leftarray[i++]
        else
            Array[k++] <- Rightarray[j++]
    }
    while (i < nL) {
        Array[k++] <- Leftarray[i++]
    }
    while (j < nR) {
        Array[k++] <- Rightarray[j++]
    }    
}  

Mergesort(Array) {
    n <- length(Array)
    if (n < 2)
        return
    mid <- n / 2
    Leftarray <- array of size (mid)
    Rightarray <- array of size (n-mid)
    for i <- 0 to mid-1
        Leftarray[i] <- Array[i]
    for i <- mid to n-1
        Right[i-mid] <- Array[mid]
    Mergesort(Leftarray)
    Mergesort(Rightarray)
    Merge(Leftarray, Rightarray) 
}    
Créé 20/10/2018 à 03:31
source utilisateur
Dans d'autres langues...                            


2 réponses

voix
2

La complexité du temps mergesort est O (NLGN), qui est une connaissance fondamentale. Fusionner Trier la complexité de l'espace sera toujours O (n), y compris avec des tableaux. Si vous dessinez l'arbre espacer, il semble bien que la complexité de l'espace est O (NLGN). Cependant, comme le code est un code de profondeur d'abord, vous serez toujours le long d'une seule étendez branche de l'arbre, par conséquent, l'utilisation de l'espace total requis sera toujours limitée par O (3n) = O (n).

Par exemple, si vous dessinez l'arbre de l'espace, il semble que c'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 (log n) => la complexité de l'espace est O (nlogn + n) = O (nlogn). Cependant, ce n'est pas le cas dans le code réel car il n'exécute pas en parallèle. Par exemple, dans le cas où N = 16, voici comment le code pour mergesort exécute. N = 16.

                       16
                      /
                     8
                    /
                   4
                 /
                2
               / \
              1   1

remarquez comment nombre d'espace utilisé est 32 = 2n = 2 * 16 <3n

Ensuite, il fusion vers le haut

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

qui est 34 <3n. Ensuite, il fusion vers le haut

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

36 <16 * 3 = 48

puis fusionner vers le haut

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

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

dans un cas plus grand, n = 64

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

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

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

Par conséquent, la complexité de l'espace est toujours limité par O (3n) = O (n), même si vous mettre en œuvre avec des tableaux aussi longtemps que vous nettoyer l'espace utilisé après la fusion et non d'exécuter du code en parallèle, mais séquentiel.

est donnée ci-dessous par exemple de ma mise en œuvre:

Créé 16/11/2018 à 18:47
source utilisateur

voix
1

Cette mise en œuvre MergeSortest tout à fait inefficace dans l' espace de mémoire et a quelques bugs:

  • la mémoire n'est pas libéré, je suppose que vous comptez sur la collecte des ordures.
  • le réseau cible Arrayne sont pas transmises au Mergepar MergeSort.

Un espace supplémentaire dans la quantité de la taille de l' Arrayest affecté par , MergeSortpour chaque niveau de récurrence, donc au moins deux fois la taille de la matrice initiale ( 2 * N ) est nécessaire, si la collecte des ordures est optimal, par exemple si elle utilise des chiffres de référence et jusqu'à N * log2 (N) d' espace est utilisé si le ramasse-miettes est paresseux. Cela est beaucoup plus que nécessaire, comme une mise en œuvre rigoureuse peut utiliser aussi peu que N / 2 d' espace.

Créé 20/10/2018 à 06:51
source utilisateur

Cookies help us deliver our services. By using our services, you agree to our use of cookies. Learn more