Ch1. 배열과 문자열
코딩 인터뷰 완전 분석(저 : 게일 라크만 맥도웰) 참조
해시테이블
해시테이블(파이썬의 dict)은 키와 값으로 대응되는 자료구조이다.
해시코드 충돌로 인해 최악의 수행 시간은 O(N)이지만, 일반적으로 탐색 시간은 O(1)이다.
python dict time complexity에서 시간 복잡도를 확인할 수 있다.
리스트
가변 크기의 자료구조를 원할 때는 리스트(배열)을 사용하게 된다.
리스트는 O(1)의 접근 시간을 유지한다.
리스트의 크기를 두배로 늘리는 시간은 O(n)이지만, 자주 발생하는 일이 아니라서 상환 입력 시간은 O(1)이 된다.
- Go 를 생각해보자. 슬라이스에 아이템을 하나씩 append 하다가 처음에 정의한 슬라이스의 크기보다 더 들어가야 된다면 그때, 슬라이스의 크기가 두배 늘어나는 상황이다.
상환 입력 시간이 O(1)인 이유
크기가 N인 배열을 생각해보자. N개의 원소를 삽입하기 위해 얼마나 많은 원소를 복사해야 하는지 역으로 계산할 수 있다.
1
2
3
4
5
6
7
8마지막 배열 크기 증가 : n/2 개의 원소 복사
이전 배열 크기 증가 : n/4 개의 원소 복사
이전 배열 크기 증가 : n/8 개의 원소 복사
.
.
.
두 번쨰 배열 크기 증가 : 2 개의 원소 복사
첫 번째 배열 크기 증가 : 1 개의 원소 복사즉, N개의 원소를 삽입하기 위해 복사해야 하는 원소의 총 개수는 1+2+…N/8+N/4+N/2 이며 이는 N보다 작다.
따라서, O(N)이 소요되는 삽입 연산도 존재하기는 하지만 평균적으로 삽입 연산은 O(1)이 소요된다.