자료구조란?
데이터를 조직하는 방법
자료구조 연산
- 읽기 - 자료구조 내 특정 위치를 찾아보는 것 (ex. 위치를 주면 값을 반환)
- 검색 - 자료구조 내 특정 값을 찾는 것 (ex. 값을 주면 위치를 반환)
- 삽입 - 자료구조에 새로운 값을 추가하는 것
- 삭제 - 자료구조에서 값을 제거하는 것
속도측정
연산이 얼마나 빠른가? (x)
→ 얼마나 많은 단계가 필요한지
자료구조의 시간복잡도
- 읽기
컴퓨터는 딱 한 단계로 배열에서 읽을 수 있다.
? → 컴퓨터는 모든 메모리 주소에 한 번에 갈 수 있다.
컴퓨터는 배열을 할당할 때 어떤 메모리 주소에서 시작하는지도 기록해 둔다.
(ex. 인덱스 3에 있는 값을 찾으라고 요청하면 컴퓨터는 인덱스 0의 메모리 주소를 가져와 3을 더한다.)
한단계로 끝나는 연산은 당연히 가장 빠른 연산 유형 중 하나이다
- 검색
배열에 특정 값이 있는지 알아본 후, 있다면 어떤 인덱스에 있는지 찾는 것
컴퓨터에서 배열은 아래와 같이 보인다. (index는 보이지만, 값은 보이지 않음)
해당 배열 안에서 찾고 싶은 ‘value’를 찾으려면 앞에서부터 하나씩 까봐야안다.
3 번째 index에 value라는 값이 있었다면 총 4개의 셀을 확인했으므로, 4단계가 걸렸다고 할 수 있다.
컴퓨터가 한 번에 한 셀씩 확인하는 방법 → 선형검색
선형검색은 최대 N개의 단계가 필요하다.
- 삽입
배열에 새 데이터를 삽입하는 연산은 배열의 어디에 데이터를 삽입하는가에 따라 효율성이 다르다.
컴퓨터의 또 다른 특징 ) 배열을 할당할 때, 항상 배열의 크기를 기록한다!
배열의 맨 뒤에 데이터를 삽입할 때는 1단계면 된다.
하지만, 배열의 맨 처음이나 중간에 데이터를 삽입하면 문제가 달라진다.(삽입할 공간을 만들기 위해 많은 데이터 조각을 이동시켜야 하므로 단계가 늘어난다)
ex) 위 배열에서 2번째 index 자리에 새 셀을 넣는다고하면 4를 한칸, 3을 한칸, 2를 한칸 총 3번의 이동이 일어나고, 새로운 셀을 넣는 1번의 연산이 일어나 총 4단계가 일어난다.
배열 삽입에서 최악의 시나리오, 즉 삽입에 가장 많은 단계가 걸리는 시나리오는 데이터를 배열의 맨 앞에 삽입할 때이다!
→ 배열 앞에 삽입하면 배열 . 내모든 값을 한 셀씩 오른쪽으로 옮겨야 하기 때문이다.
원소 N개를 포함하는 배열에서 최악의 시나리오일 때 삽입에는 N+1단계가 걸린다. (N번 이동 후, 1삽입)
- 삭제
배열의 삭제는 특정 인덱스의 값을 제거하는 과정
해당 배열에서 셀을 삭제하는 것은 기술적으로 한 단계만 걸린다. (문제는 비어있는 셀을 매꾸는 작업 즉 왼쪽으로 옮기는 작업이 필요하다.)
삽입과 비슷하게 원소 삭제에서 최악의 시나리오는 배열의 첫 번째 원소를 삭제하는 것이다. 이렇게 되면 인덱스 0이 비게 되고, 남아있는 모든 원소를 왼쪽으로 이동시켜 빈공간을 채워야한다.
원소 N개를 포함하는 배열에서 삭제에 필요한 최대 단계 수는 N단계라고 할 수 있다.
집합? (중복값을 허용하지 않는 자료구조)
배열 기반 집합 ( 단순 리스트로 배열과 거의 비슷 )(중복값 허용 x)
‘중복금지’라는 제약이 하나 추가된 것만으로, 집합의 효율성이 크게 달라진다.
집합 ( 읽기, 검색, 삭제는 일반 배열과 시간복잡도가 동일)
but, 삽입은 다르다.
집합에서 삽입을 할 때는, 먼저 이 값이 이미 집합에 들어 있는지 결정해야한다. (중복데이터 막기)
집합에 새 값이 없을 때에만 컴퓨터는 삽입을 허용
모든 삽입에는 검색이 우선
집합의 끝에 삽입하려면 원소 N개에 대해 최대 N+1 단계가 필요하다. (N = 검색, 1= 삽입)
but, 최악의 시나리오
집합의 맨 앞에 삽입하는 경우
→ 컴퓨터는 N개를 검색해서 집합이 그 값을 포함하지 않음을 확인한 후, 또 다른 N단계로 모든 데이터를 오른쪽으로 옮겨야하며, 마지막 단계에서 새 값을 삽입해야한다. 총 2N+1(N(검색)+N(이동)+1(삽입))이다. (일반 배열은 N+1 ⇒ n개 이동 후, 첫번째 셀에 삽입)
마무리
자료구조의 성능 측정은 연산에 필요한 단계 수를 구하는 게 핵심이다.
