java algorithms collections
1.0.0
주니어 Java 개발자 역할을위한 기술 인터뷰를위한 맞춤형 데이터 모음.
여기에서 전체 목록을 참조하십시오
n 시간 복잡성 - 입력의 요소 수.
n 공간 복잡성 - 입력을 나타내는 데 필요한 비트 단위의 입력 크기.
| 유형 | 이름 | 설명 | 상태 | 예 |
|---|---|---|---|---|
O(1) | 일정한 시간 | 알고리즘은 입력 크기에 관계없이 매번 같은 횟수로 실행됩니다. | 훌륭한 | 키에 의해 해시 테이블에서 검색하십시오 |
O(log n) | 로그 시간 | 입력 데이터의 크기 증가에 비해 실행 시간이 매우 느리게 증가합니다. | 훌륭한 | 이진 검색 (평균) |
O(n) | 선형 시간 | 실행 시간은 입력 데이터의 크기에 비례합니다. | 좋은 | 무차별 인력 검색 |
O(n + k) | 결합/부가 시간 | 두 개의 개별 입력의 복잡성 | 좋은 | 계산 정렬 |
O(n log n) | 유사성 시간 | 입력 크기가 증가함에 따라 로그 성장으로 인해 문제를 해결하는 데 필요한 분열 수가 느리게 증가합니다. | 나쁜 | 정렬, 힙 정렬을 병합하십시오 |
O(n^2) | 2 차 시간 | 각 요소에 대한 중첩 반복 또는 비교가 포함됩니다 | 끔찍한 | 선택 정렬 |
O(2^n) | 지수 시간 | 입력의 가능한 모든 조합의 철저한 검색 또는 열거가 포함되면 실행 시간이 기하 급수적으로 증가합니다. | 끔찍한 | TSP (동적 프로그래밍) |
O(n!) | 계승 시간 | 입력의 가능한 모든 조합의 철저한 검색 또는 열거가 포함되면 실행 시간은 요소 적으로 증가합니다. | 끔찍한 | TSP (Brute Force) |
| 유형 | 이름 | 설명 | 상태 | 예 |
|---|---|---|---|---|
O(1) | 일정한 공간 | 알고리즘에는 입력 크기에 관계없이 고정 된 양의 추가 메모리가 필요합니다. | 훌륭한 | 힙 정렬 |
O(log n) | 로그 공간 | 공간 사용량은 입력 데이터의 크기 증가에 비해 천천히 증가합니다. | 훌륭한 | 빠른 정렬 |
O(n) | 선형 공간 | 공간 사용량은 입력 크기로 선형으로 스케일링됩니다 | 좋은 | 정렬을 병합하십시오 |
O(n + k) | 결합/부가 공간 | 공간 사용량은 n 과 k 의 합으로 선형으로 스케일링됩니다. | 나쁜 | radix 정렬 |
| 용어 | 정의 | 예 |
|---|---|---|
| 추상 데이터 유형 (ADT) | 특정 구현 세부 사항보다는 동작 및 운영에 중점을 둔 데이터 유형에 대한 높은 수준의 설명을 나타냅니다. | 스택, 큐, 사전, 시퀀스, 세트 |
| 데이터 구조 | 효율적인 운영을 용이하게하기 위해 특정 데이터 유형 구현, 특정 방식으로 데이터 구성 및 저장을위한 기술 또는 전략 | 배열, 링크 된 목록, 해시 테이블, 나무 (이진 검색 트리, 힙, 빨간색/검은 나무 |
| 유형 | 중복 요소 | 요소의 순서 | 특정 순서로 추가/제거해야합니다 |
|---|---|---|---|
| 목록 | 허용된 | 인덱스에 의해 | 아니요 |
| 지도 | 값을 허용합니다 | Java는 키의 hashcode ()를 사용하여 순서를 결정합니다. | 아니요 |
| 대기줄 | 허용된 | 정의 된 순서로 검색됩니다 | 예 |
| 세트 | 금지 | 트리셋에서만 | 예 |
| 유형 | 인터페이스 | 정렬? | 호출 hashCode() ? | compareTo() 호출? |
|---|---|---|---|---|
| 배열 목록 | 목록 | 아니요 | 아니요 | 아니요 |
| Linkedlist | 목록, deque | 아니요 | 아니요 | 아니요 |
| Arraydeque | 대기열, deque | 아니요 | 아니요 | 아니요 |
| 해시 세트 | 세트 | 아니요 | 예 | 아니요 |
| 트리 셋 | set, sortedset | 예 | 아니요 | 예 |
| LinkedHashSet | 세트 | 아니요 | 예 | 아니요 |
| 해시 맵 | 지도 | 아니요 | 예 | 아니요 |
| LinkedHashMap | 지도 | 아니요 | 예 | 아니요 |
| 트리 맵 | 지도, SortedMap | 예 | 아니요 | 예 |
정렬과 관련된 데이터 구조는 널 값을 허용하지 않습니다.
