자바 2 분 검색 트 리,링크 의 실현 을 바탕 으로 하 는 집합 Set 복잡 도 분석 사례 상세 설명
두 가지 집합 류 의 복잡 도 분석
네자바 바 텀 은 이 진 트 리 를 기반 으로 집합 과 맵 을 실현 합 니 다. 자바 바 텀 은 링크 를 바탕 으로 집합 과 맵 을 실현 합 니 다.에서 2 분 검색 트 리 와 링크 를 바탕 으로 집합
Set
을 실 현 했 고 이 절 에서 두 가지 집합 류 의 복잡 도 분석 을 분석 했다.테스트 내용:자바 바 텀 은 이 진 트 리 를 기반 으로 집합 과 맵 을 실현 합 니 다.과자바 바 텀 은 링크 를 바탕 으로 집합 과 맵 을 실현 합 니 다.에 사 용 된 책.
테스트 방법:두 가지 집합 류 를 테스트 하여 단 어 를 찾 는 데 사용 되 는 시간
// Set<String> set: LinkedListSet BSTSet
private static double testSet(Set<String> set, String filename) {
//
long startTime = System.nanoTime();
System.out.println("Pride and Prejudice");
// ArrayList
ArrayList<String> words1 = new ArrayList<>();
// word1
FileOperation.readFile(filename, words1);
System.out.println("Total words : " + words1.size());
// for , word words
// ArrayList words1 word
for (String word : words1)
set.add(word);//
System.out.println("Total different words : " + set.getSize());
//
long endTime = System.nanoTime();
return (endTime - startTime) / 1000000000.0;//
}
public static void main(String[] args) {
//
BSTSet<String> bstSet = new BSTSet<>();
double time1 = testSet(bstSet, "pride-and-prejudice.txt");
System.out.println("BSTSet:" + time1 + "s");
System.out.println("――――――――――――――――――――");
//
LinkedListSet<String> linkedListSet = new LinkedListSet<>();
double time2 = testSet(linkedListSet, "pride-and-prejudice.txt");
System.out.println("linkedListSet:" + time2 + "s");
}
결과:BSTSet 의 속도 가 LinkedListed 보다 빠르다.집합 시간 복잡 도 분석:
1.링크 상황
2.이 진 트 리 의 경우
이 진 트 리 를 바탕 으로 하 는 상황 에서 이 진 트 리 의 깊이 를 증가,조회,삭제 하 는 것 은 이 진 트 리 의 깊이 와 관련 이 있 고 매번 작업 은 뿌리 노드 에서 특정한 서브 트 리 의 잎 노드 사이 에서 작업 하 며 시간 복잡 도 는
0(h)
이 고h
이 진 트 리 의 높이(층수)를 나타 낸다.이 진 트 리 검색 복잡 도 는 다음 과 같 습 니 다.
2.1 링크 상황 에서 n 과 이 진 트 리 의 h 관 계 를 연구한다.
다음은 n 과 h 관 계 를 유도 합 니 다.
2.1.1 만 이 진 트 리 의 상황 을 분석(최 적 상황)
만 이 진 트 리(각 노드 에 좌우 노드 가 있 고 잎 노드 를 제외 하고)를 이용 하여 분석 한 이 유 는 만 이 진 트 리 가 극단 적 인 상황 이기 때문에 다음 과 같다.
위의 그림 에서
h
에 대해 모두 몇 개의 노드 가 다음 과 같이 추론 된다.노드 개수 가
n
개 라 고 가정 하면 다음 과 같은 관계 가 있다.모두
log
의 관계 에 대해 기본 수 는 다소 영향 을 주지 않 는 다.log
는 다음 과 같다.2.1.2 한 아이의 경우-이 진 트 리 의 최 악의 경우(노드 수 는 그 높이 와 같다)
다음 두 갈래 검색 트 리
한 아이 만 있 는 경우 이 때 이 진 트 리 는 링크 로 퇴화 되 었 고 이때 의 시간 복잡 도 는 O(n)이다.
2.2 두 가지 집합 복잡 도 통계
2.2.1 logn 과 n 의 차이
추천 은 최고의 지지 이 고 관심 은 가장 큰 격려 이다.친애 하 는 친구 여,정원 에서 당신 을 만 나 게 되 어 매우 영광 입 니 다.
이 절 에 관련 된 소스 주 소 는https://github.com/FelixBin/dataStructure/tree/master/src/SetPart입 니 다.
자바 알고리즘 과 관련 된 내용 에 관심 이 있 는 독자 들 은 본 사이트 의 주 제 를 볼 수 있 습 니 다.자바 데이터 구조 및 알고리즘 튜 토리 얼,자바 조작 DOM 노드 기술 총화,자바 파일 과 디 렉 터 리 작업 기법 집합과자바 캐 시 작업 기법 집합
본 고 에서 말 한 것 이 여러분 의 자바 프로 그래 밍 에 도움 이 되 기 를 바 랍 니 다.
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
JPA + QueryDSL 계층형 댓글, 대댓글 구현(2)이번엔 전편에 이어서 계층형 댓글, 대댓글을 다시 리팩토링해볼 예정이다. 이전 게시글에서는 계층형 댓글, 대댓글을 구현은 되었지만 N+1 문제가 있었다. 이번에는 그 N+1 문제를 해결해 볼 것이다. 위의 로직은 이...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.