자료구조7 해시테이블 해시함수 특정 값을 원하는 범위의 자연수로 바꿔주는 함수 해시함수의 조건 한 해시 테이블의 해시함수는 결정론적이어야한다. 결과 해시값이 치우치지 않고 고르게 나온다. 빨리 계산 할수 있어야 한다. 해시테이블 고정된 크기의 배열을 만든다. 해시함수를 이용해서 key를 원하는 범위의 자연수로 바꾼다. 해시함수 결과 값 인덱스에 key-value쌍을 저장한다. 충돌 (collision) 사용하고 있는 인덱스에 또 다른 키 밸류 쌍을 저장하는 것 Chaining 충돌이 일어나는 값들을 사슬처럼 묶는것 링크드 리스트를 통해 Chaining한 해시테이블 시간 복잡도 아래의 세연산은 모두 링크드 리스트의 탐색을 동반하기 때문에 O(n)의 시간 복잡도를 지닌다. 동작 (Operation) 시간 복잡도 탐색 (searc.. 2024. 1. 9. 배열 C 배열과 파이썬 리스트 차이 C배열 : 메모리에 값자체를 연속적으로 저장한다 파이썬 리스트 : 메모리에 레퍼런스를 저장하고 이 레퍼런스는 다른 값들을 가르킨다. 💡 배열에서 값을 받아오거나 저장하는건 램의 특성으로 O(1)으로 접근 가능하다. 배열탐색 선형 탐색이라고도 불리며 인덱스 0번부터 차례대로 배열을 살펴본다. ⇒ 즉, 탐색은 O(n)이 걸린다. 정적 배열 : 크기가 고정된 배열 동적 배열 : 크기가 변하는 배열 정적 배열로 만들어진 자료 구조 정적 배열의 크기를 상황에 맞게 조절한다. 동적 배열 연산 추가연산 정적배열에 남는 공간이 있을때 O(1) 정적배열이 꽉찼을 때 : O(n) 분할 상환 분석 연산을 n번 했을 때 총 드는 시간 X를 n으로 나눠주는 할부 개념 ⇒ 최악의 경우로 시간 복잡도.. 2024. 1. 7. 이전 1 2 다음
