java - 计算链表交集的空间复杂度是多少

Question

我正在计算 2 个链表的交集，其中一个链表的大小为“n”，第二个链表的大小为“m”。下面的代码将较小链表的项目存储在一个集合中。因此空间复杂度为 O(m)，其中 m < n，又名，m 是较小链表的长度。

但是，有可能 2 个链表是相等的，m = n。那么复杂度是 O(n) 吗？

public IntersectionAndUnionLinkedList<T> intersection(IntersectionAndUnionLinkedList<T> list) {
        final Set<T> items = new HashSet<>();

        Node<T> firstSmall = null;
        Node<T> firstBig   = null;

        if (size <= list.size) {
            firstSmall = first;
            firstBig = list.first;
        } else {
            firstSmall = list.first;
            firstBig = first; 
        }


        Node<T> n = null;
        for (n = firstSmall; n != null; n = n.next) {
                items.add(n.item);
        }

        IntersectionAndUnionLinkedList<T> intersectionlist = new IntersectionAndUnionLinkedList<>();
        for (n = firstBig; n != null; n = n.next) {
            if (items.contains(n.item)) {
                intersectionlist.add(n.item);
            }
        }

        return intersectionlist;
    }

Answer 1

万一 m=n，O(m)=O(n)，但可以肯定地说内存复杂度是 O( m) 因为它是唯一真实的因素。

另一方面，HashSet<T>在极端情况下可能会降低内存效率:毕竟它使用了桶，桶可能会以糟糕的方式填充。这取决于 HashMap<T> 的确切实现.尽管人们仍然期望线性内存复杂度为 O(m)。