Расчет временной сложности Итерационного алгоритма

Question

Я имею дело с проблемой, когда в какой-то момент сливаются два отдельных списка. Следующее изображение иллюстрирует эту концепцию.

Я полагаю, чтобы найти и вернуть узел, где они оба пересекаются. Мне дается ссылка на главу обоих списков. Ниже приведен алгоритм.

public Node getNodeIntersection(Node head1, Node head2) 
{ 
    Node temp1 = head1; 
    Node temp2 = head2; 
    /*Get lengths of both the lists*/ 
    int len1 = this.getLength(temp1); 
    int len2 = this.getLength(temp2); 

    int diff = getAbs(len1,len2); //get absolute difference of the two lengths 

    //Iterate through the bigger list first so both list have equal nodes left 
    if(len1 > len2) 
    { 
     int count = 0; 
     while(count < diff) 
     { 
      temp1 = temp1.getNext(); 
      count++; 
     } 
    } 
    else 
    { 
      int count = 0; 
      while(count < diff) 
     { 
      temp2 = temp2.getNext(); 
      count++; 
     } 
    } 

    Node nIntersect = null; 
    while(temp1 != temp2) 
    { 
     temp1 = temp1.getNext(); 
     temp2 = temp2.getNext(); 

     if(temp1 == temp2) 
     { 
      nIntersect = temp1; 
     } 

    } 

    return nIntersect; 

} 

У меня возникли проблемы с вычислением временной сложности для этого. Мое понимание состоит в том, что я сначала нахожу длины обоих списков, которые будут N + N. Затем я перебираю более крупный список, который снова является N, а затем я повторяю оба списка до тех пор, пока они не пересекаются, что снова является N узлами. Я думал, что эта сложность по времени для этого алгоритма будет O (N). К моему удивлению, после решения этого алгоритма, я нашел похожие решения в некоторых блогах, а временная сложность для этого - O (M + N). Я не понимаю, почему? Я думал, что по мере того, как N переходит в бесконечность, большее значение будет доминировать, так что это будет O (max (m, n)), который будет либо O (n), либо O (m), в зависимости от того, какой из них больше. Может ли кто-нибудь прояснить это для меня?

Answer 1

O(max(n, m))O(n + m) т.к. max(n, m) <= n + m. Это точная оценка, потому что max(n, m) >= (n + m)/2.