[자료구조] 집합

중복 값을 허용하지 않는 자료구조.

 

집합의 연산 효율성은 읽기, 검색, 삭제는 배열과 같으나 삽입의 경우 크게 달라진다.

 

n사이즈의 집합에 새로운 값을 맨 앞에 넣으려고 하면 효율성이 어떻게 될까?

 

일단 집합은 중복값을 허용하지 않으므로 검색을 실행한다. 중복값이 없다면 n단계가 실행된다.

그 후, 맨 앞에 넣기 위해서는 n+1단계가 필요하다. 따라서 집합의 삽입의 최악의 경우는 2n+1단계가 필요하다.

배열의 입력이 최악 n+1단계 필요하다 했으므로 집합이 2배 가까이 느림을 알 수 있다.

 

그러나 느리다고 사용하지 않는 게 아닌 중복 데이터가 없을 때는 사용해야 한다.