以下代码的复杂性

Question

我被赋予以下任务：

给出了-2个列表。第一个列表的大小为N1，第二个列表的尺寸为N2。每个列表的元素不相同。编写一段代码，用第一个和第二个列表中的元素创建一个新列表。此列表也不应有相同的元素。还要估计代码的复杂性。

我编写了以下代码：

public class Lists {    
    static ArrayList<Integer> getNewList(ArrayList<Integer> list1, 
                                         ArrayList<Integer> list2) {
        ArrayList<Integer> tmp = new ArrayList<>();
        for (Integer i : list1) {
            tmp.add(i);
        }
        for (Integer i : list2) {
            if (!list1.contains(i)) 
                tmp.add(i);
        }
        return tmp;
    }

    public static void main(String[] args) { 
        Integer[] arr1 = {1, 2, 3, 14, 15, 16};        
        Integer[] arr2 = {3, 6, 7, 8, 14};
        ArrayList<Integer> list1 = new ArrayList<>(Arrays.asList(arr1));
        ArrayList<Integer> list2 = new ArrayList<>(Arrays.asList(arr2));
        for (Integer i : getNewList(list1, list2)) {
            System.out.print(i + " ");
        }
    }
}

并假设 getNewList 方法的执行时间与 N1*N2 成正比。在回复中，我收到以下内容，没有任何解释 - “你错了，这段代码的复杂性不是 N1*N2”。

那么有人能告诉我什么是正确的答案吗？并解释复杂性是如何决定的？

Answer 1

我肯定在这里也看到了O（N1*N2）的复杂性。我猜你的教授忽略了包含调用的成本如下：

for (Integer i : list2) {
    if (!list1.contains(i)) 
        tmp.add(i);
}

在 ArrayList 上包含 O（N） 复杂度。由于 list2 上的循环也是 O（N），因此最终得到 O（N1 * N2）。

Answer 2

嗯，你这个问题的简短回答是:复杂度是N1 (N2*N1)/2 N3(新列表的大小)，应该是O(N1*N2)

故障：

for (Integer i : list1) {
  tmp.add(i);
} 
-> clearly, this is N1

for (Integer i : list2) {
  if (!list1.contains(i)) 
    tmp.add(i);
} 
-> list2 iteration => N2
-> for each of this iteration, you call .contain method 
   which uses sequential search, resulting in N1/2 iterations (on average)
-> So, you get N2*N1/2

在main中，您有一个循环，从0迭代到N3（这是新List的长度）

所以，总的来说，你得到N1（N2*N1）/2 N3，应该是O（N1*N2）

Answer 3

代码的复杂度为< code>O(N1*N2)，但是通过使用< code>HashSet来确定哪些数字出现在两个列表中，你可以做得更好:

static ArrayList<Integer> getNewList(ArrayList<Integer> list1, 
                                     ArrayList<Integer> list2) {
    ArrayList<Integer> tmp = new ArrayList<>();
    HashSet<Integer> dups = new HashSet<>();
    tmp.addAll(list1);
    dups.addAll(list1);
    for (Integer i : list2) {
        if (!dups.contains(i)) 
            tmp.add(i);
    }
    return tmp;
}

这将为您提供O（N1 N2）运行时间，因为在HashSet中插入和查找需要预期的O（1）时间。