algorithm - los - espacio de busqueda en optimizacion

Combina el tiempo y la complejidad del espacio

Question

Tomemos esta implementación de Merge Sort como ejemplo

void mergesort(Item a[], int l, int r) {
if (r <= l) return;
int m = (r+l)/2;
mergesort(a, l, m);  ------------ (1)
mergesort(a, m+1, r); ------------(2)
merge(a, l, m, r);

a) La complejidad del tiempo de esta clasificación de fusión es O (nlg (n)). ¿La paralelización (1) y (2) dará algún beneficio práctico? Teóricamente, parece que después de paralelizarlos también terminarías en O (nlg (n). ¿Pero prácticamente podemos obtener alguna ganancia?

b) La complejidad de espacio de este Ordenamiento de fusión aquí es O (n). Sin embargo, si elijo realizar una ordenación de fusión en el lugar utilizando listas vinculadas (no estoy seguro de que pueda hacerse con matrices de manera razonable) la complejidad del espacio se convertirá en O (lg (n)), ya que debe tener en cuenta el tamaño del marco de la pila de recursión ? ¿Podemos tratar a O (lg (n)) como constante ya que no puede ser más de 64? Puede que haya entendido mal esto en un par de lugares. ¿Cuál es exactamente el significado de 64?

c) http://www.cprogramming.com/tutorial/computersciencetheory/sortcomp.html dice que la ordenación de combinación requiere espacio constante utilizando listas enlazadas. Cómo ? ¿Trataron a O (lg (n) constante?

d) [Se agregó para obtener más claridad] Para el cálculo de la complejidad del espacio, ¿es correcto asumir que la matriz de entrada o la lista ya están en la memoria? Cuando hago cálculos de complejidad, siempre calculo el espacio "Extra" que necesitaré, además del espacio que ya ocupa la entrada. De lo contrario, la complejidad del espacio siempre será O (n) o peor.

Answer 1

Complejidad del espacio: es nlogn si se crean subarray / sublist en cada nivel (niveles de logn * n espacio requerido en cada nivel => logn * n). Y si no, y se considera el espacio de pila, sería logn para LinkedList y n (n + logn = n) para Array. Complejidad del tiempo: nlogn para el peor y el promedio de los casos

Answer 2

El peor de los casos de clasificación de mezcla: O (n log n) , el mejor de los casos de clasificación de combinación: O (n log n), la variante natural O (n) , el rendimiento promedio de clasificación de combinación: O (n log n) , Complejidad de espacio en el peor de los casos de ordenación de combinación: О (n) total, O (n) auxiliar

Answer 3

La complejidad del tiempo MergeSort es O (nlgn), que es un conocimiento fundamental. La complejidad del espacio Merge Sort siempre será O (n) incluido con arreglos. Si dibuja el árbol de espacio, parecerá que la complejidad del espacio es O (nlgn). Sin embargo, como el código es un código de Primero en profundidad, siempre se expandirá a lo largo de una rama del árbol, por lo tanto, el uso de espacio total requerido siempre estará delimitado por O (3n) = O (n).

Por ejemplo, si dibuja el árbol de espacio, parece que es 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

donde la altura del árbol es O (logn) => la complejidad del espacio es O (nlogn + n) = O (nlogn). Sin embargo, este no es el caso en el código real, ya que no se ejecuta en paralelo. Por ejemplo, en el caso donde N = 16, así es como se ejecuta el código para mergesort. N = 16.

                           16
                          /
                         8
                        /
                       4
                     /
                    2
                   / /
                  1   1

observe cómo el número de espacio utilizado es 32 = 2n = 2 * 16 <3n

Entonces se fusiona hacia arriba.

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

que es 34 <3n. Entonces se fusiona hacia arriba.

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

36 <16 * 3 = 48

entonces se fusiona hacia arriba

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

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

en un caso más grande, n = 64

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

que es 64 * 3 <= 3 * n = 3 * 64

Puedes probar esto por inducción para el caso general.

Por lo tanto, la complejidad del espacio siempre está limitada por O (3n) = O (n), incluso si implementa con arreglos, siempre que limpie el espacio usado después de la combinación y no ejecute el código en paralelo sino en secuencia.

A continuación se muestra un ejemplo de mi implementación:

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://.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;
}

Espero que esto ayude! =)

Pronto Chee Loong,

Universidad de Toronto

Answer 4

a) Sí, en un mundo perfecto tendrías que hacer registros n combinaciones de tamaño n, n / 2, n / 4 ... (o mejor dicho 1, 2, 3 ... n / 4, n / 2 , n - no pueden ser paralelizados), lo que da O (n). Todavía es O (n log n). En un mundo no tan perfecto, no tiene un número infinito de procesadores y el cambio de contexto y la sincronización compensa cualquier ganancia potencial.

b) La complejidad del espacio es siempre Ω (n) ya que tiene que almacenar los elementos en algún lugar. La complejidad de espacio adicional puede ser O (n) en una implementación usando arreglos y O (1) en implementaciones de listas vinculadas. En la práctica, las implementaciones que usan listas necesitan espacio adicional para los punteros de la lista, así que a menos que ya tenga la lista en la memoria, no debería importar.

edite si cuenta los marcos de pila, entonces es O (n) + O (log n), por lo que aún es O (n) en el caso de arreglos. En el caso de listas es O (log n) memoria adicional.

c) Las listas solo necesitan que se cambien algunos punteros durante el proceso de fusión. Eso requiere una memoria adicional constante.

d) Es por eso que en el análisis de complejidad de ordenación por fusión la gente menciona "requisitos de espacio adicional" o cosas por el estilo. Es obvio que tienes que almacenar los elementos en algún lugar, pero siempre es mejor mencionar "memoria adicional" para mantener a los puristas a raya.

Answer 5

a) Sí, por supuesto, paralelizar el tipo de combinación puede ser muy beneficioso. Sigue siendo nlogn, pero su constante debe ser significativamente menor.

b) La complejidad del espacio con una lista enlazada debe ser O (n), o más específicamente O (n) + O (logn). Tenga en cuenta que eso es un +, no un *. No te preocupes mucho por las constantes al hacer un análisis asintótico.

c) En el análisis asintótico, solo el término dominante en la ecuación importa mucho, por lo que el hecho de que tengamos un + y no un * lo hace O (n). Si estuviéramos duplicando todas las listas secundarias, creo que sería un espacio O (nlogn), pero una ordenación inteligente basada en listas vinculadas puede compartir regiones de las listas.