algorithm - idioma - organizar listas mailchimp

Gran complejidad O para fusionar dos listas

Question

Dado 2 listas enlazadas individuales ya ordenadas, combine las listas.

Ejemplo:
list1: 1 2 3 5 7
list2: 0 4 6 7 10
---> 0 1 2 3 4 5 6 7 7 10

A pesar del hecho de que la solución es bastante simple y hay varias implementaciones diferentes del problema con o sin recurrencia (como esta http://www.geeksforgeeks.org/merge-two-sorted-linked-lists/ see Method 3 ),

Me preguntaba cuál sería la gran complejidad de esta implementación:

1. Si una de las listas está vacía, simplemente devuelva la otra
2. De lo contrario, inserte cada nodo de la segunda lista en el primero usando la función sortedinsert, que básicamente escanea la lista hasta encontrar la posición correcta. Como las 2 listas ya están ordenadas, no es necesario comparar cada vez que el nodo con todos los nodos en la primera lista, puedo comenzar la comparación desde el último nodo agregado.

ej .: continuando con el ejemplo anterior si 4 ya se ha agregado, puedo comenzar con seguridad la siguiente comparación de 4:
list1: 0 1 2 3 4 5 7
list2: 6 7 10
ahora compara 6 con 4 en lugar de 1 2 3 4 ...

Si quisiera comparar un elemento con todos los elementos en la primera lista, sería O (m * n) con m = # list2 yn = # list1, pero considerando esta "optimización" ¿cuál es la complejidad?

Implementación:

// Insert a new node in a sorted list
int sortedInsert(struct ListNode **head, struct ListNode* newNode) {
    int headUpdated = 0;
    struct ListNode *current;

    // The list is empty or the new element has to be added as first element
    if (*head == NULL || (*head)->data >= newNode->data) {
        newNode->next = *head;
        *head = newNode;
        headUpdated = 1;
    }
    else {
        // Locate the node before the point of insertion
        current = *head;
        while (current->next != NULL && current->next->data < newNode->data)
            current = current->next;

        newNode->next = current->next;
        current->next = newNode;
    }

    return headUpdated;
}


struct ListNode *mergeLists(struct ListNode *head1, struct ListNode *head2) {
    if (head1 == NULL)
        return head2;

    if (head2 == NULL)
        return head1;

    // Store the node in the first list where to start the comparisons
    struct ListNode *first = head1;

    while (head2) {
        struct ListNode *head2Next = head2->next;

        printf("Adding %d starting comparison from %d/n", head2->data, first->data);
        if (sortedInsert(&first, head2))
            head1 = first;

        first = head2;
        head2 = head2Next;
    }

    return head1;
}

Answer 1

En realidad, el algoritmo de fusión que tienes aquí es O(m + n) , no O(m * n) .

Como tiene un puntero al último nodo insertado y comienza a buscar el lugar para insertar el siguiente nodo a partir de ese momento, la cantidad total de

current = current->next

operaciones en sortedInsert es como máximo m + n - 1 (duración del resultado menos uno). El número de operaciones de inserción (vinculación de los next punteros) es n (longitud de la segunda lista). Para cada comparación

current->next->data < newNode->data

la siguiente operación es una inserción o una current = current->next , por lo que el número de comparaciones es como máximo

m + 2*n - 1

Digamos que la lista resultante comienza con m_0 elementos de la primera lista, luego n_1 elementos del segundo, luego m_1 del primero, n_2 del segundo, ..., n_r del segundo, y finalmente m_r del primero. m_0 y m_r pueden ser 0, todos los demás números son estrictamente positivos.

El primer elemento del bloque n_1 se compara con cada elemento del bloque m_0 y el primer elemento del bloque m_1 . Todos los demás elementos de ese bloque se comparan con su predecesor en la segunda lista, y el primer elemento del bloque m_1 [a menos que r = 1 y m_1 = 0 , en cuyo caso hay menos comparaciones].

Eso hace que m_0 + 1 + (n_1 - 1)*2 = m_0 + 2*n_1 - 1 comparaciones (o menos).

Para los bloques n_k posteriores, el primer elemento se compara con el último elemento del bloque n_(k-1) , todos los elementos del bloque m_(k-1) y el primer elemento del bloque m_k [si es que existe] . Los elementos adicionales del bloque son todos comparados con su predecesor en la lista 2, y el primer elemento del bloque m_k [si eso existe], que hace

 1 + m_(k-1) + 1 + (n_k - 1)*2 = m_(k-1) + 2*n_k

comparaciones (o menos). Dado que todas las comparaciones implican al menos un elemento de la segunda lista, el número total de comparaciones es como máximo

m_0 + 2*n_1 - 1 + m_1 + 2*n_2 + m_2 + 2*n_3 + ... + m_(r-1) + 2*n_r <= m + 2*n - 1.

Podemos mejorarlo ligeramente iniciando

    struct ListNode *first = head1;

y eliminando el

    if (!first)
        first = head1;

prueba del bucle