중복 문자열 복잡성 검색

Question

중복 요소를 찾고 부울 값을 반환하는 메서드를 작성하는 작업이 있습니다.

아래 코드는 내가 가지고있는 코드입니다.

import java.util.ArrayList; 
import java.util.List; 

public class DuplicateEle { 
    public static void main(String args[]) { 
     String[] arr = { "hello", "hi", "hello", "howru" }; 
     DuplicateEle de = new DuplicateEle(); 
     for (int i = 0; i < arr.length; i++) { 
      boolean isDup = de.isDuplicate(arr[i]); 
      System.out.println(arr[i]+" is duplicate :" +isDup); 
     } 
    } 

    List<String> dList = new ArrayList<String>(); 

    private boolean isDuplicate(String str) { 
     boolean isDup = false; 
     if (dList.contains(str)) { 
      isDup = true; 
     } else 
      dList.add(str); 
     return isDup; 
    } 

} 

예상대로 작동합니다. 출력 :

hello is duplicate :false 
hi is duplicate :false 
hello is duplicate :true 
howru is duplicate :false 

나는 위의 코드에 대한 시간 복잡도를 찾고 싶어요. 이 튜토리얼은 시간 복잡성에 대해서는 one과 같은 방식으로 작동합니다.

누군가 위의 코드에 대한 의견을 알려주고 시간 복잡성에 대한 이해를 도울 수 있습니까?

미리 감사드립니다.

Answer 1

코드가 너무 복잡하므로 HashSet<String>을 사용하면 고유성을 보장하고 요소가 이미 세트에 있는지 여부를 반환합니다. 그것은 단지 다음 전체 '비싼'할 equals를 사용할 필요, 버킷을 찾을 문자열의 int 해시를 사용으로 HashSet를 사용

public class DuplicateEle { 
    public static void main(String args[]) { 
     Set<String> seen = new HashSet<>(); 
     String[] arr = { "hello", "hi", "hello", "howru" }; 

     for (String word : arr) { 
     boolean unique = seen.add(word); 
     System.out.printf("%s is duplicate: %b%n", word, !unique); 
     } 
    } 
} 

이 매우 효율적입니다 같습니다.

Answer 2

즉, n은 검사 할 요소의 수이고 m은 가장 긴 단어의 크기입니다. 따라서 요소 배열을 살펴보고 각 요소에 대해 dList에 있는지 확인하십시오.

시작시 빈 시간이므로 요소를 추가하십시오. 그래서, 질문은, 방법이 얼마나 빠릅니다 contains입니다. ArrayList의 소스 코드를 살펴보면 배열을 통해 각 요소가 equal인지 확인하고 끝에서부터 시작하여 각 문자를 검사하여 완료됩니다 (먼저 동일한 크기인지 확인) .

그래서 최악의 경우 모든 요소는 크기가 같고 첫 번째 요소가 다릅니다. 그래서 첫 번째 요소에서는 아무것도하지 않으므로 기본 작업은 1로 계산됩니다. 2 단계에서 1 단계 검사를 수행하고 3 단계에서는 2 단계 검사를하고 1 단계에서 n-1 검사를 수행합니다. .

0+1+2+...+n-1 = n(n-1)/2 

지금, 최악의 시나리오는, 각 요소는 동일한 크기와 그들이 첫 번째 요소에서 다른, 그래서 당신은 크기 m의 또 다른 루프를 가지고 : 그래서, 당신은. 여기서 m은 평균 문자열 크기 또는 문자열의 끝에서 다른 char의 위치에 대한 통계적 예상을 나타낼 수도 있습니다.

따라서 O(mn^2)이지만 임의의 숫자가 m 인 경우이를 Ω(n^2)이라고 할 수 있습니다.

하지만 좋은 소식이 있습니다. HashSet을 사용하면 더 빠른 방법이 있습니다. HashSet을 사용하여 dList를 변경하고 초기 목록을 살펴 가면서 각 요소를 배치해야하므로 각 요소를 확인하는 작업은 O(1)에서 완료됩니다. 즉, 전체 속도는 O(n)이됩니다.