Сложность времени?

Question

Проблема заключалась в том, чтобы найти пересечение 2 отсортированных связанных списков и сохранить общие элементы в третьем списке.

Мой подход состоял в том, чтобы сделать временные указатели temp1 и temp2 инициализирующими оба значения для head1(заголовок списка 1) и head2 (заголовок списка 2) соответственно. А затем обходит оба списка и сравнивает элементы и соответственно сдвигает temp1 и temp2. Код работает нормально.

Тестовый пример: Первый связанный список => 1-> 2-> 3-> 4-> 6 Второй связанный список будет 2-> 4-> 6-> 8, затем функция должна создать и вернуть третий список как 2-> 4->6.

Но меня смущает сложность времени: O (m + n) или O (мин (m, n)) ?(m, n - количество элементов в списке 1 и списке 2).

Мой код:

#include<stdio.h>
#include<stdlib.h>

/* Link list node */
struct Node
{
    int data;
    struct Node* next;
};
void append(struct Node** head_ref, int new_data)
{
    /* 1. allocate node */
    struct Node* new_node = (struct Node*) malloc(sizeof(struct Node));

    struct Node *last = *head_ref;  /* used in step 5*/

    /* 2. put in the data  */
    new_node->data  = new_data;

    /* 3. This new node is going to be the last node, so make next 
          of it as NULL*/
    new_node->next = NULL;

    /* 4. If the Linked List is empty, then make the new node as head */
    if (*head_ref == NULL)
    {
       *head_ref = new_node;
       return;
    }  

    /* 5. Else traverse till the last node */
    while (last->next != NULL)
        last = last->next;

    /* 6. Change the next of last node */
    last->next = new_node;
    return;    
}

struct Node* sortedIntersect(struct Node* head1,struct Node*head2)
{
    struct Node*head3=NULL;
    struct Node*temp1=head1;
    struct Node*temp2=head2;
    while(temp1!=NULL&&temp2!=NULL)
    {
        if(temp1->data<temp2->data)
        {if(temp1->next!=NULL)
            temp1=temp1->next;
            else
            break;
        } 
        else if(temp1->data>temp2->data)
        {
            if(temp2->next!=NULL)
            temp2=temp2->next;
            else{
                break;
            }
        }
        else 
        {
            append(&head3,temp1->data);
            temp1=temp1->next;
            temp2=temp2->next;
        }
    }
    return head3;
}


/* Function to insert a node at the beginging of the linked list */
void push(struct Node** head_ref, int new_data)
{
    /* allocate node */
    struct Node* new_node = (struct Node*) malloc(sizeof(struct Node));

    /* put in the data */
    new_node->data = new_data;

    /* link the old list off the new node */
    new_node->next = (*head_ref);

    /* move the head to point to the new node */
    (*head_ref) = new_node;
}

/* Function to print nodes in a given linked list */
void printList(struct Node *node)
{
    while (node != NULL)
    {
        printf("%d ", node->data);
        node = node->next;
    }
}


int main()
{
    /* Start with the empty lists */
    struct Node* a = NULL;
    struct Node* b = NULL;
    struct Node *intersect = NULL;

    /* Let us create the first sorted linked list to test the functions
    Created linked list will be 1->2->3->4->5->6 */
    push(&a, 6);
    push(&a, 5);
    push(&a, 4);
    push(&a, 3);
    push(&a, 2);
    push(&a, 1);

    /* Let us create the second sorted linked list
    Created linked list will be 2->4->6->8 */
    push(&b, 8);
    push(&b, 6);
    push(&b, 4);
    push(&b, 2);

    /* Find the intersection two linked lists */
    intersect = sortedIntersect(a, b);

    printf("\n Linked list containing common items of a & b \n ");
    printList(intersect);

    return 0;
}

Answer 1

Это проблема, которую можно решить в O(m+n).

Однако это решение не O(m+n).Каждый элемент, который вы добавляете в метод intersectSorted, добавляется с помощью метода append, который пересекает весь текущий список вывода.

Таким образом, сложность времени составляет O((m+n)log(min(m,n))

Answer 2

В worst case это будет O(m+n)

example: {1,3,5,7} {2,4,6,8}
, в этом случае вы пройдете оба списка.

В averageв этом случае это будет

O(min(m,n) + number of times you don't increment the smaller list)

example : {1,2,3,4,6} {2,4,6,8,9,10}
, в этом случае вы завершаете цикл, как только достигнете конца первого списка с выравниванием, но между ними вы увеличиваете второй список без увеличения первогоlist.

В best случае это будет O(min(m,n))

example: {1,2,3} {1,2,3,4,}
, в этом случае вы прекратите цикл после достижения концапервый список.

Answer 3

Как и в каждой итерации while, по крайней мере один из указателей переходит к следующему, и условие прекращения while заключается в том, что ни один из указателей не достигнут до конца, временная сложность будет O(min(m,n)).