해시 테이블 대 이진 검색 트리의 큰 o

StackOverflow https://stackoverflow.com/questions/859782

  •  21-08-2019
  •  | 
  •  

문제

더 오래 걸리나요?

이진 검색 트리에 저장된 모든 항목을 정렬 된 순서로 인쇄하거나 해시 테이블에 저장된 모든 항목을 정렬 된 순서로 인쇄합니다.

해시 테이블이 정렬되지 않았기 때문에 해시 테이블의 항목을 정렬 순서로 인쇄하는 데 시간이 더 걸리나요? 그리고 BST는?

도움이 되었습니까?

해결책

당신이 올바른지. 해시블은 자연적인 정렬 순서가 아닌 일부 해시 함수에 의해 정렬되므로 모든 항목을 추출하고 O (nlogn)를 정렬 해야하는 반면 O (Nlogn)를 정렬해야합니다. N).

그러나 Java에는 예를 들어, 링크드 하쉬 세트와 링크드 하쉬 맵이있어 해시의 장점을 제공하지만 추가 된 순서대로 이동할 수 있으므로 정렬하고 트래버스 할 수 있습니다. 해시별로 항목을 추출 할뿐만 아니라 정렬 된 순서.

다른 팁

수정, 해시 테이블은 원하는 방식으로 "정렬"되지 않습니다. 해시 테이블의 요소는 일반적으로 분류되지 않지만 일반적으로 배열은 종종 일종의 주변에 있습니다. 그러나 해시 함수에 따라 배열되며, 이는 일반적으로 유사한 문구에 대해 크게 다릅니다. 그것은 인간이 사용할 수있는 메트릭에 의해 분류가 아닙니다.

컬렉션으로 수행하는 주요 일이 정렬 된 순서로 인쇄하는 경우 일부 유형의 BST를 사용하는 것이 가장 좋습니다.

이진 검색 트리는 깊이의 첫 번째 트래버스를 수행하면 정렬 된 순서로 항목을 찾을 수있는 방식으로 저장됩니다 (일관된 비교 기능이 있다고 가정). 단순히 나무에 이미 반환하는 아이템의 큰 O는 나무를 가로 지르는 큰 O 일 것입니다.

당신은 해시 테이블에 대해 맞습니다. 정렬되지 않습니다. 실제로, 평범한 해시 테이블에 모든 것을 열거하려면 모든 버킷을 확인하여 거기에 무엇이 있는지 확인한 다음 꺼낸 다음 얻는 것을 정렬해야합니다. 정렬 된 목록을 얻기위한 많은 작업이 있습니다.

해시 테이블이 정렬 된 데이터가 아니기 때문에 해시 테이블에 저장된 인쇄 정렬 데이터는 느리게됩니다. 특정 항목을 찾는 빠른 방법을 제공합니다. 안에 "큰 o 표기법"이 품목은 일정한 시간 (예 : O) 시간에 찾을 수 있다고합니다.

반면에 데이터가 이미 정렬되었으므로 "로그 시간"(O (log n))의 이진 검색 트리에서 항목을 찾을 수 있습니다.

따라서 정렬 된 목록을 인쇄하는 것이 목표라면 정렬 된 순서 (즉, 이진 트리)로 데이터를 저장하는 것이 훨씬 좋습니다.

즐기다,

Robert C. Cartaino

이것은 몇 가지 흥미로운 질문을 제기합니다. 다음을 고려할 때 검색 트리가 여전히 더 빠르나요?

  1. 해시 테이블과 BST 모두에 대한 설정 시간을 통합합니까?
  2. 해시 알고리즘이 정렬 된 단어 목록을 생성하는 경우. 기술적으로, 당신은 알고리즘을 사용하는 해시 테이블을 만들 수 있습니다. 이 경우 BST 대 해시 테이블의 속도는 해시 테이블을 정렬 된 순서로 채우는 데 걸리는 시간으로 내려야합니다.

또한 Skip List 대 바이너리 트리의 관련 고려 사항을 확인하십시오. 목록 대 바이너리 트리를 건너 뜁니다

라이센스 : CC-BY-SA ~와 함께 속성
제휴하지 않습니다 StackOverflow
scroll top