以下代碼的複雜性

給定-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」。

那麼有人可以告訴什麼是正確的答案？並解釋複雜性如何確定？

來源

2016-07-24 nik

那麼，簡短的回答你的問題是：複雜性是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

在你有一個循環，從0迭代主直至N3（這是新的列表的長度）

因此，總體上你得到N1 +（N2 * N1）/ 2 + N3，它應該在O（N1 * N2）中

來源

2016-07-24 08:38:13

的代碼的複雜性是O(N1*N2)，但你可以在這兩個列表做用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)運行時間，因爲插入和查找預計在HashSetO(1)時間。

來源

2016-07-24 08:20:19 Eran

感謝@ Slanec的解釋，我重新檢查的contains(Object obj)實施的JDK，發現它是如下

public boolean contains(Object obj) { 
    return indexOf(obj) >= 0; 
} 

public int indexOf(Object obj) { 
    if (obj == null) { 
     for (int i = 0; i < size; i++) 
      if (elementData[i] == null) 
       return i; 

    } else { 
     for (int j = 0; j < size; j++) 
      if (obj.equals(elementData[j])) 
       return j; 

    } 
    return -1; 
}

顯然，contains(Object obj)的時間複雜度爲O（n）。（我認爲這是Ø （1）第一）

因此，代碼的時間複雜度應該O（N1 N2 *），但不爲O（n）。

來源

2016-07-24 08:25:07 Gearon

除非你能用實際的解釋證明我錯了，我會說沒有。第二個循環對'list1'中的'list2'中的每個元素執行'contains（）'檢查。列表中的contains（）調用是線性的，O（N1），循環本身顯然也是線性的。所以複雜度是N1 * N2。 –

我在這裏肯定也看到了O(N1 * N2)的複雜性。我猜你的教授忽略了contains通話費用如下所示：

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

contains上的ArrayList是O(N)複雜。由於您在list2上的循環也是O(N)，所以最終的結果是O(N1 * N2)。

來源

2016-07-24 08:32:37 Vikram

以下代碼的複雜性

回答

相關問題