计算迭代算法的时间复杂度

Question

我正在处理两个单向链表在某个点合并的问题。下图说明了这个概念。

我想找到 return 它们相交的节点。我只得到了两个列表的头部的参考。以下是我想出的算法。

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.

计算迭代算法的时间复杂度

Calculating time complexity of a Iterative algorithm

java

algorithm

linked-list