다음 코드의 복잡성

Question

다음 작업을 받았습니다.

주어진 -2 목록. 첫 번째 목록의 크기는 N1이고 두 번째 목록의 크기는 N2입니다. 각 목록에는 동일한 요소가 없습니다. 첫 번째 및 두 번째 목록의 요소로 새 목록을 만드는 코드를 작성하십시오. 이 목록에는 동일한 요소가 없어야합니다. 코드의 복잡도도 추정하십시오.

는 I가 따라와 코드 해주기

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

음, 귀하의 질문에 짧은 대답은 : 복잡성 N1 + (N2 * N1)/2 + O에 있어야 N3 (새 목록의 크기), (N1 * N2)

고장입니다 : 당신은 0에서 반복 루프를 메인에서

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 

---

까지

(새로운 목록의 길이) N

그래서, 전반적인 당신은 N1 + (N2 * N1이)/2 + O에서 (N1 * N2)

Answer 2

코드의 복잡성이 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) 실행 시간을 줄 것이다 O(1) 시간은 HashSet으로 예상됩니다.

Answer 3

덕분에 @ Slanec의 설명은, 내가 JDK에 contains(Object obj)의 구현을 다시 확인하고 분명히

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)입니다. (나는 O라고 생각 (1) 처음에)

그래서 코드 시간 복잡도)은 O (N1 * N2) 아니지만 O (N이어야한다.

Answer 4

여기에도 역시 O(N1 * N2) 복잡함이 있습니다. 나는 당신의 교수는 다음의 contains 전화의 비용을 간과 같은데요 : ArrayList의에

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

contains는 O(N) 복잡하다. list2 이상의 루프도 O(N)이므로 O(N1 * N2)이됩니다.