algorithm - idioma - organizar listas mailchimp
Gran complejidad O para fusionar dos listas (1)
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:
- Si una de las listas está vacía, simplemente devuelva la otra
- 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;
}
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