728x90
CS/자료구조
-
Hash란?CS/자료구조 2022. 6. 13. 22:04
배열 0 1 2 3 … 9270 … 9999 Koguri@koguri.com 배열은 원소 하나를 저장하거나 검색할 때 자료의 개수와 비례하는 시간이 걸리게 됩니다. koguri@koguri.com이 맞는지 확인할때 하나하나 비교해야하기 때문에 O(N)의 시간이 걸리게됩니다. 배열보다 조금 더 빨리 자료를 저장, 검색 할 방법은 없을까? 란 고민 끝에 나온 자료구조가 트리입니다. 트리 트리는 원소 하나를 저장하거나 검색하는 데 평균 O(logN)의 시간이 걸립니다. 레드 블랙 트리처럼 균형 잡힌 트리는 최악의 경우에도 O(logN)의 시간이 걸리게 됩니다. 하지만 트리도 자료의 크기가 커지면 저장 및 검색에 오랜 시간이 걸리게 됩니다. 저장된 자료의 양에 상관없이 원소 하나를 저장하고 검색하는 것을 상수 ..