내 프로그램의 복잡성 결정?

Question

내 프로그램이 두 목록 사이에 대칭적인 차이를 가져옵니다.

import java.util.*; 

    /** 
    * A class to find the symmetric difference between two lists. 
    */ 

    public class SymDifference 
    { 
    /** 
    * Finds the symmetric difference between two sorted lists. 
    * 
    * @param L1  first list 
    * @param L2  second list 
    * @param Result list with the symmetric difference 
    */ 
    static <AnyType extends Comparable<? super AnyType>> void symDifference(List<AnyType> L1, List<AnyType> L2, 
                      List<AnyType> Result) 
    { 
     //create two iterators to go through the list 
     ListIterator<AnyType> iterL1 = L1.listIterator(); 
     ListIterator<AnyType> iterL2 = L2.listIterator(); 

     //create two anytype objs 
     AnyType itemL1 = null; 
     AnyType itemL2 = null; 

     //gets the first two items of the lists 
     if (iterL1.hasNext() && iterL2.hasNext()) 
     { 
      itemL1 = iterL1.next(); 
      itemL2 = iterL2.next(); 
     } 

     //use a while loop to compare elements of lists 
     while (itemL1 != null && itemL2 != null) 
     { 
      int compareResult = itemL1.compareTo(itemL2); 

      //elements are the same so go on to the next items 
      if (compareResult == 0) 
      { 
       //get next item for list L1 
       if (iterL1.hasNext()) 
       { 
        itemL1 = iterL1.next(); 
       } 
       else 
       { 
        itemL1 = null; 
       } 
       //get next item for list L2 
       if (iterL2.hasNext()) 
       { 
        itemL2 = iterL2.next(); 
       } 
       else 
       { 
        itemL2 = null; 
       } 
      } 
      // the item of L1 comes after the item of L2, add item from L2 to results 
      else if (compareResult < 0) 
      { 
       Result.add(itemL1); 

       //get next item for list L1 
       if (iterL1.hasNext()) 
       { 
        itemL1 = iterL1.next(); 
       } 
       //get next item for list L2 
       else 
       { 
        itemL1 = null; 
       } 
      } 
      // the item of L1 comes before the item of L2, add item from L1 to results 
      else 
      { 
       Result.add(itemL2); 

       //get next item for list L1 
       if (iterL2.hasNext()) 
       { 
        itemL2 = iterL2.next(); 
       } 
       //get next item for list L2 
       else 
       { 
        itemL2 = null; 

       } 
      } 

     } 

     //add remaining items from list L1 
     while (itemL1 != null) 
     { 

      Result.add(itemL1); 
      if (iterL1.hasNext()) 
      { 
       itemL1 = iterL1.next(); 
      } 
      else 
      { 
       itemL1 = null; 
      } 

     } 

     //add remaining items from list L2 
     while (itemL2 != null) 
     { 

      Result.add(itemL2); 
      if (iterL2.hasNext()) 
      { 
       itemL2 = iterL1.next(); 
      } 
      else 
      { 
       itemL2 = null; 
      } 

     } 
    } 

    //tester class 
    public static void main(String[] args) 
    { 
     ArrayList<Integer> a = new ArrayList<>(); 
     a.add(1); 
     a.add(3); 
     a.add(5); 
     a.add(7); 
     a.add(9); 
     a.add(12); 

     ArrayList<Integer> a2 = new ArrayList<>(); 
     a2.add(1); 
     a2.add(2); 
     a2.add(3); 
     a2.add(9); 
     a2.add(20); 
     ArrayList<Integer> results = new ArrayList<>(); 

     symDifference(a, a2, results); 
     Collections.sort(results); // sort the results 
     System.out.println(results.toString()); 

    } 
} 

내 코드 O(n)가 : 여기 내 코드? 나는 그것이 확실하다. 그러나 나는 확실하지 않다. 나는 아직도 시간 복잡성을 완전히 이해하지 못한다. 나는 목록을 가로 지르면 O(n)을 얻는다.하지만 두 목록을 가로 지르면 바뀌는 지 알 수 없다. 목록이 하나의 루프 아래에서 가로지기 때문에 O(n)이라고 생각합니다. 어떤 도움을 많이 주시면 감사하겠습니다! 시간 내 줘서 고마워! m가 첫 번째 목록의 길이이고 n이 두 번째 목록의 길이입니다

Answer 1

예 코드는

복잡성은 두 개의 정렬 된 배열 병합의 경우와 동일합니다 ... O(m+n)이다. 두리스트 사이의 공통 숫자를 최종 결과에 추가하지 마십시오.