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;
}

老实说，我确信第一个算法比第二个算法更好，因为它的性能。我想使用 SPACE 和 TIME COMPLEXITY 来演示这种性能，我没有主导这些主题。

根据资料，这个解法应该是时间复杂度:O(N)。但我不太确定第一个算法会是 O(N)。

Answer 1

第一种算法对headA和headB扫描一次求长度，然后跳过较长链的多余元素，然后并行扫描两条链。时间复杂度与链的长度成正比，所以是 O(N)。扫描列表 2 次、3 次或 5 次并不重要，只要该次数不变，时间复杂度仍然是 O(N)。

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

这两种算法的空间复杂度都是 O(1)，因为您在两者(一堆局部变量)中都使用常量存储，无论输入列表的大小如何，它们都不会改变。