Page 33 -

집합의 끝에 값을 삽입하는 게 최선의 시나리오인데도 불구하고 원래 5개의 원소가 있는 집합에
여전히 6단계를 수행해야 했다. 즉, 최종 삽입 단계를 수행하기 전에 5개의 원소를 전부 검색해야
했다.

바꿔 말해 집합의 끝에 삽입하려면 원소 N개에 대해 최대 N+1단계가 필요하다. 값이 집합에 없
음을 확인하는 데 N단계의 검색을, 이어서 실제 삽입에 1단계를 쓰기 때문이다. 맨 끝에 삽입하는
데 1단계밖에 걸리지 않는 일반적인 배열과 대조된다.

값을 집합의 맨 앞에 삽입하는 최악의 시나리오일 때 컴퓨터는 셀 N개를 검색해서 집합이 그 값을

포함하지 않음을 확인한 후, 또 다른 N단계로 모든 데이터를 오른쪽으로 옮겨야 하며, 마지막 단
계에서 새 값을 삽입해야 한다. 총 2N+1단계다. 맨 앞에 삽입하는 데 N+1단계밖에 걸리지 않는
일반적인 배열과 대조된다.

그렇다면 삽입이 일반적인 배열보다 집합에서 느리다는 이유만으로 집합을 쓰지 말아야 할까? 물
론 아니다. 중복 데이터가 없어야 할 때는 집합이 답이다(바라건대, 언젠가는 내 전화번호부도 고
쳐지기를…). 하지만 이러한 요구사항이 없다면 집합 삽입보다 배열 삽입이 더 효율적이므로 배열

이 나을 수 있다. 애플리케이션의 요구사항을 먼저 분석한 후 어떤 자료 구조가 더 적합한지 결정
해야 한다.

1.9 마무리 DATA STRUCTURES AND ALGORITHMS

자료 구조의 성능 측정은 연산에 필요한 단계 수를 구하는 게 핵심이다. 프로그램이 어마어마한
부하를 감당할지 혹은 중단돼 버릴지는 프로그램에 꼭 맞는 자료 구조를 선택했느냐에 따라 바뀔
수 있다. 1장에서는 특별히 배열과 집합을 예로 들어 단계 수를 구하는 성능 분석을 사용해 어떤
구조가 주어진 애플리케이션에 적합한지 설명했다.

자료 구조의 시간 복잡도를 어떻게 고려하는지 이제 막 알았으니 같은 방법으로 서로 경쟁하는(심
지어 같은 자료 구조를 쓰는) 알고리즘을 비교해 코드가 최고의 속도와 성능을 내게끔 할 수도 있

다. 이에 대해서는 2장에서 다루겠다.

046