두 개의 공통된 요소를 찾고 싶습니다. LinkedHashSet<String>
주로 주로 자체 함수를 작성했지만 비용은 o (n^2)입니다. 그럼 난 retainAll()
자바 내장 된 더 나은 솔루션을 발견했다. 이 기능의 비용이 얼마인지 궁금합니다. O (n) 또는 o (n^2)?Collection.retainAll (Collection)의 비용은 무엇입니까
1
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
은 메서드를 호출하는 컬렉션의 크기입니다.
관련 문제
- 1. 비용은
- 2. 전산 비용은
- 3. Scala에서 Collection의 index로부터 옵션을 얻는 방법은 무엇입니까?
- 4. Struts2에서 빈 Collection의 유효성을 검사하는 방법은 무엇입니까?
- 5. 크기/비용은
- 6. 평가 비용은
- 7. 문자열의 문자 교체 비용은?
- 8. #define의 비용은 얼마입니까?
- 9. Interlock.Exchange 및 Garbage Collection의 안전성
- 10. Meteor Collection의 색인에 문서 삽입
- 11. 색인을 아는 Collection의 요소를 얻으시겠습니까?
- 12. Flex : Array Collection의 두 요소 교환하기
- 13. JavaEE 애플리케이션에 클래스를 추가하는 비용은 무엇입니까
- 14. Django의 unique_together 기능의 성능 비용은 무엇입니까
- 15. 이진 트리를 트래버스하는 최소 비용은 무엇입니까
- 16. Ruby에서 재귀의 비용은 얼마입니까?
- 17. 프로세서 비용은 어느정도입니까?
- 18. node.js의 require() 비용은 얼마입니까?
- 19. 쿼리 당 비용은 얼마입니까?
- 20. Eshop 카트의 총 비용은
- 21. Heroku 교통 비용은 얼마입니까?
- 22. CGAffineTransformMakeRotation() 비용은 얼마입니까?
- 23. x86_64의 인터럽트 비용은 얼마입니까
- 24. AWS Cloud9 비용은 사용합니까?
- 25. Java Collection의 Vector Class가 멀티 스레딩에서 성능이 떨어지는 이유는 무엇입니까?
- 26. Observable Collection의 Item 속성을 Switch 상태에 바인딩하는 방법은 무엇입니까?
- 27. Power Collection의 OrderedMultiDictionary를 우선 순위 큐로 사용해야합니까?
- 28. Java Collection의 초기 용량을 결정할 수 있습니까?
- 29. C#에서 Collection의 하위 집합을 통해 열거합니까?
- 30. RestKit : Map 2 차원 배열 (Collection의 Collection)
['AbstractCollection'] (http://grepcode.com/file/repository.grepcode.com/java/root/jdk/openjdk/8u40-b25/java/util/AbstractCollection.java#)의 구현을 사용합니다. 404). 그것은 일정한 시간의'contains'와'remove'를 사용하기 때문에 선형적인 것처럼 보입니다. –
@AndyTurner : 감사합니다. – user1836957