컴퓨터 알고리즘 초급 #8 ( 해쉬 알고리즘 1 )
Direct-address Tables - 크기가 |U|인 테이블 T를 생성하고 key k를 slot k에 저장하는 방식 - 중복되는 key가 없다고 가정 이러한 테이블의 장점은 키 값만 알면 데이터를 바로 찾을 수 있으므로 시간복잡도가 엄청나게 빠르다 .O(1) Direct addressing의 공간 복잡도 - O(|U|) - 실제 공간 사용을 전체 공간으로 나눈 |K|/|U|를 적재율이라고 한다. - 만약 적재율이 낮다면, 실제로 대부분의 공간은 낭비된다. Hash Tables 해쉬함수라는 것은 임의의 크기의 데이터를 받아서 그 데이터를 고정된 크기로 바꿔주는 것을 해쉬라고 부른다. actual keys를 어떠한 해쉬함수에 넣어서 거기에 해당하는 해쉬값에 넣어준다. 문제점은 동일한 해쉬값이 생길 수 ..
Study/소프트웨어
2020. 7. 8. 16:57