java如何确定这两种算法的空间和时间复杂性？

Question

今天我在HackerRank练习一个算法：https://www.hackerrank.com/challenges/find-the-merge-point-of-two-joined-linked-lists

我决定用两种方法解决这个问题

第一种算法，基于弗洛伊德的算法：

/*
  Insert Node at the end of a linked list 
  head pointer input could be NULL as well for empty list
  Node is defined as 
  class Node {
     int data;
     Node next;
  }
*/
int FindMergeNode(Node headA, Node headB) {
    // Complete this function
    // Do not write the main method. 
    int length1 = countLength(headA);
    int length2 = countLength(headB);
    int d = Math.abs(length1 - length2);

    return (length1 > length2) ?
        findIntersection(d, headA, headB) : findIntersection(d, headB, headA);
}

int countLength(Node head) {
    Node current = head;
    int counter = 0;

    while (current != null) {
        current = current.next;
        counter++;
    }

    return counter;
}

int findIntersection(int d, Node headA, Node headB) {
    Node currentA = headA;
    Node currentB = headB;

    for (int i = 0; i < d; i++) {
        currentA = currentA.next;
    }

    while (currentA != null && currentB != null) {
        if (currentA == currentB) return currentA.data;

        currentA = currentA.next;
        currentB = currentB.next;
    }

    return -1;
}

第二种算法，使用一个外循环和一个内循环：

/*
  Insert Node at the end of a linked list 
  head pointer input could be NULL as well for empty list
  Node is defined as 
  class Node {
     int data;
     Node next;
  }
*/
int FindMergeNode(Node headA, Node headB) {
    Node currentA = headA;

    while (currentA != null) {
        Node currentB = headB;

        while (currentB != null) {
            if (currentA == currentB) {
                return currentA.data;
            }

            currentB = currentB.next;
        }

        currentA = currentA.next;
    }

    return -1;
}

老实说，我相信第一种算法比第二种算法更好，因为它的性能。我想用空间和时间的复杂性来展示这种性能，我并没有主导这些主题

根据材料，这个解决方案应该是时间复杂度：O（N）。但我不太确定第一个算法是否是O（N）

Answer 1

第一个是O（N），其中N是抽象的两个列表长度中的最大值。由于您有两个for循环，每个循环的开销最大为N，因此在最坏的情况下，第一个算法需要2 N个循环才能结束。既然O隐藏常数因子，算法就是O（N）

Answer 2

第一种算法扫描headA和headB一次以找到长度，然后跳过较长链的额外元素，然后并行扫描两条链。时间复杂度与链的长度成正比，所以它是O（N）。不管你扫描列表2、3或5次，只要这个数字不变，时间复杂度仍然是O（N）

第二种算法更糟糕，对于合并点之前headA中的每个元素，它扫描整个headB。在最坏的情况下，当列表在最后一个节点不相交时，它将扫描headB的所有元素，以查找headA的每个元素。所以这个的时间复杂度是O（N^2）

这两种算法的空间复杂度都是O（1），因为这两种算法（一组局部变量）都使用常量存储，无论输入列表的大小，都不会改变