Большая сложность для слияния двух списков

Question

Учитывая, что 2 отдельных списка уже отсортированы, объедините списки.

Пример:
песни1: 1 2 3 5 7
песни2: 0 4 6 7 10
---> 0 1 2 3 4 5 6 7 7 10

Несмотря из того, что решение довольно просто и есть несколько различных реализаций задачи с использованием или без использования рекурсии (как это http://www.geeksforgeeks.org/merge-two-sorted-linked-lists/ см Способ 3),

мне было интересно, что будет O большая сложность реализации этого:

1. Если один из списков пуст просто возвращает другой
2. В противном случае вставьте каждый узел второго списка в первом, используя функцию sortedInsert, которая в основном сканирование списка, пока правая позиция не найдена. Поскольку два списка уже отсортированы, нет необходимости сравнивать каждый раз, когда узел со всеми узлами в первом списке, я могу начать сравнение с последним добавленным узлом.

например: продолжается и в предыдущем примере, если 4 было уже добавлено могу смело начать следующее сравнение с 4:
песни1: песни2: 6-10
сейчас сравните 6 с 4 вместо этого с 1 2 3 4 ....

Если бы я сравнил один элемент со всеми элементами в первом списке, это было бы O (m * n) с m = # list2 и n = # list1, но учитывая эту «оптимизацию», какая сложность?

Реализация:

// 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

На самом деле алгоритм слияния вы имеете здесь O(m + n), не O(m * n).

Поскольку у вас есть указатель на последний вставленный узел, и начать искать место, чтобы вставить следующий узел от этого на, общее количество

current = current->next 

операций в sortedInsert находится в наиболее m + n - 1 (длина результата минус один). Количество операций вставки (перемещение указателей next) равно n (длина второго списка). Для каждого сравнения

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

следующая операцией является либо вставкой или current = current->next, поэтому количество сравнений в наиболее

m + 2*n - 1 

Будет говорить, что полученный список начинается с m_0 элементами из первых список, затем n_1 элементов со второго, затем m_1 с первого, n_2 со второго, ..., n_r со второго, затем, наконец, m_r с первого. m_0 и m_r может быть 0, все остальные цифры строго положительны.

Первый элемент блока n_1 сравнивается с каждым элементом блока m_0 и первым элементом блока m_1. Все остальные элементы этого блока сравниваются со своим предшественником во втором списке и с первым элементом блока m_1 [кроме r = 1 и m_1 = 0, и в этом случае сравнения меньше].

Это делает сравнения m_0 + 1 + (n_1 - 1)*2 = m_0 + 2*n_1 - 1 (или меньше).

Для получения более поздних n_k блоков, первый элемент сравнивается с последним элементом n_(k-1) блока, все элементы m_(k-1) блока, и первый элемент m_k блока [если существует]. Дальнейшие элементы блока все по сравнению с их предшественником в списке 2, а первый элемент m_k блока [если существует], что делает

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

сравнений (или меньше). Поскольку все сравнения включают по меньшей мере один элемент из второго списка, общее количество сравнений в наиболее

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. 

Мы можем немного улучшить его intialising

struct ListNode *first = head1; 

и удаление

if (!first) 
     first = head1; 

тест из петли.