차집합

Computer Science/자료구조

6. 집합 ADT

이번에는 집합 ADT입니다. 먼저 특징을 살펴보자면, 집합 ADT는 유일한 개체들을 담아야 하고 이러한 개체들을 정렬된 리스트로 표현한다는 것이 되겠습니다. 각 개체들은 유일해야 하고, a b c d 나 1 2 3 4처럼 정렬되어야 합니다. 이런 집합 ADT의 주요 함수들은 이렇습니다. set union(B) set intersect(B) set subtract(B) union은 집합 B와 합집합을 반환하고, intersect는 집합 B와 교집합을 반환합니다. 그리고 subtract는 집합 B를 차감한 차집합을 반환합니다. 그리고 이러한 메서드들의 실행시간은 최대 O(|A| + |B|)가 되어야 합니다. 즉, 각 집합들의 최대 원소들의 수를 합한 것이 최대 실행시간이 된다는 것입니다. 이외의 함수들도 써..

SpaceCowboy
'차집합' 태그의 글 목록