1
두 개의 공통된 요소를 찾고 싶습니다. LinkedHashSet<String> 주로 주로 자체 함수를 작성했지만 비용은 o (n^2)입니다. 그럼 난 retainAll() 자바 내장 된 더 나은 솔루션을 발견했다. 이 기능의 비용이 얼마인지 궁금합니다. O (n) 또는 o (n^2)?Collection.retainAll (Collection)의 비용은 무엇입니까
A
답변
1
LinkedHashSet의 경우 최소한 O (N)입니다. 다른 Collection은 트리 집합과 같으며 O (NlogN)이고 나머지는 O (N^2)입니다.
참고 이러한 조치는 retainAll 메서드에 전달한 컬렉션에 따라 다릅니다. 그래서 HashSet을 전달하는 TreeSet는 O (NlogN) 될 것이며, 다른 아무것도 AbstractCollection의 구현을 보면 (NlogN)
2
O보다 더 나쁜 것, (N) O 될 것, 그것을 컬렉션의 모든 요소를 반복 처리 (즉, n) 호출되고 각 요소에 대해 다른 컬렉션에 포함되어 있는지 확인합니다 (LinkedHashSet의 경우 O (1) 연산).
결론 -이 작업은 O (n) 작업입니다. 여기서 n은 메서드를 호출하는 컬렉션의 크기입니다.
['AbstractCollection'] (http://grepcode.com/file/repository.grepcode.com/java/root/jdk/openjdk/8u40-b25/java/util/AbstractCollection.java#)의 구현을 사용합니다. 404). 그것은 일정한 시간의'contains'와'remove'를 사용하기 때문에 선형적인 것처럼 보입니다. –
@AndyTurner : 감사합니다. – user1836957