기사 제목은 다음과 같아야 합니다. Java 컬렉션 구현의 Big-O 시간 복잡성은 무엇입니까?
- Linda Hamilton원래의
- 2024-10-28 02:33:31765검색
Java Collections Framework 구현: Big-O 요약
"Java 단기 집중 강좌"를 가르칠 때 다음 사항을 알고 있어야 합니다. 다양한 컬렉션 구현과 관련된 Big-O 시간 복잡도. 청중은 Big-O 표기법에 익숙할 수 있지만 특정 컬렉션에 대한 다양한 작업의 구체적인 복잡성을 알 가능성은 거의 없습니다.
다행히도 "Java Generics and Collections"라는 책은 이러한 복잡성에 대한 귀중한 통찰력을 제공합니다. . 이 글은 책의 정보를 요약하여 각 컬렉션 유형(목록, 세트, 맵, 큐)에 대한 자세한 표를 제공합니다.
목록 구현:
| Operation | ArrayList | LinkedList | CopyOnWriteArrayList |
|---|---|---|---|
| get | O(1) | O(n) | O(1) |
| add | O(1) | O(1) | O(n) |
| contains | O(n) | O(n) | O(n) |
| next | O(1) | O(1) | O(1) |
| remove(0) | O(n) | O(1) | O(n) |
| iterator.remove | O(n) | O(1) | O(n) |
구현 설정:
| Operation | HashSet | LinkedHashSet | CopyOnWriteArraySet | EnumSet | TreeSet | ConcurrentSkipListSet |
|---|---|---|---|---|---|---|
| add | O(1) | O(1) | O(n) | O(1) | O(log n) | O(log n) |
| contains | O(1) | O(1) | O(n) | O(1) | O(log n) | O(log n) |
| next | O(h/n) | O(1) | O(1) | O(1) | O(log n) | O(1) |
| Notes | h is the table capacity |
맵 구현:
| Operation | HashMap | LinkedHashMap | IdentityHashMap | EnumMap | TreeMap | ConcurrentHashMap | ConcurrentSkipListMap |
|---|---|---|---|---|---|---|---|
| get | O(1) | O(1) | O(1) | O(1) | O(log n) | O(1) | O(log n) |
| containsKey | O(1) | O(1) | O(1) | O(1) | O(log n) | O(1) | O(log n) |
| next | O(h/n) | O(1) | O(h/n) | O(1) | O(log n) | O(h/n) | O(1) |
| Notes | h is the table capacity |
대기열 구현:
| Operation | PriorityQueue | ConcurrentLinkedQueue | ArrayBlockingQueue | LinkedBlockingQueue | PriorityBlockingQueue | DelayQueue | LinkedList | ArrayDeque | LinkedBlockingDeque |
|---|---|---|---|---|---|---|---|---|---|
| offer | O(log n) | O(1) | O(1) | O(1) | O(log n) | O(log n) | O(1) | O(1) | O(1) |
| peek | O(1) | O(1) | O(1) | O(1) | O(1) | O(1) | O(1) | O(1) | O(1) |
| poll | O(log n) | O(1) | O(1) | O(1) | O(log n) | O(log n) | O(1) | O(1) | O(1) |
| size | O(1) | O(n) | O(1) | O(1) | O(1) | O(1) | O(1) | O(1) | O(1) |
위 내용은 기사 제목은 다음과 같아야 합니다. Java 컬렉션 구현의 Big-O 시간 복잡성은 무엇입니까?의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!
성명：
본 글의 내용은 네티즌들의 자발적인 기여로 작성되었으며, 저작권은 원저작자에게 있습니다. 본 사이트는 이에 상응하는 법적 책임을 지지 않습니다. 표절이나 침해가 의심되는 콘텐츠를 발견한 경우 admin@php.cn으로 문의하세요.
관련 기사
더보기- 비트 이동과 곱셈/나눗셈: Java 및 .NET의 성능을 걱정해야 합니까?
- jconsole에 대한 JMX 원격 액세스를 활성화하고 JVM에 연결하는 방법은 무엇입니까?
- IntelliJ IDEA에서 class.getResource()가 Null을 반환하는 이유는 무엇입니까?
- 다음은 질문 형식을 포함하는 몇 가지 제목 옵션입니다. * Java는 메모리 할당 해제를 어떻게 관리합니까? (간단하고 직접적) * 개체를 Null로 설정하면 메모리 할당 해제가 보장됩니까?
- 다음은 기사 내용과 일치하는 몇 가지 질문 기반 제목입니다. * Java 코드를 프로파일링해야 합니까? 무료이고 강력한 도구인 VisualVM을 만나보세요! * 오픈 소스 Java 프로파일링을 찾고 계십니까? 바이