초록

용어보기논문에서 용어와 풀이말을 자동 추출한 결과로, 시범 서비스 중입니다. AI-Helper

프로그램 언어에서 집합을 표현하기 위한 일반적인 자료구조는 배열에 원소를나열하는 방법이다. 이 방법을 사용하면 합집합, 교집합, 차집합, 부분 집합 체크 등 집합 연산 알고리즘의 시간 복잡도가 모두 $O(n^2)$을 보인다. 그런데, 집합 원소를 정수의 비트 정보로 대응시켜 집합 연산을 구현하면 복잡도를 O(1)로 낮출 수 있음을 실험으로 확인하였다.

프로그램 언어에서 집합을 표현하기 위한 일반적인 자료구조는 배열에 원소를나열하는 방법이다. 이 방법을 사용하면 합집합, 교집합, 차집합, 부분 집합 체크 등 집합 연산 알고리즘의 시간 복잡도가 모두 $O(n^2)$을 보인다. 그런데, 집합 원소를 정수의 비트 정보로 대응시켜 집합 연산을 구현하면 복잡도를 O(1)로 낮출 수 있음을 실험으로 확인하였다.

AI 본문요약

엑셀 다운로드 AI-Helper

* AI 자동 식별 결과로 적합하지 않은 문장이 있을 수 있으니, 이용에 유의하시기 바랍니다.

• 연구 주제

문제 정의

• 이 논문에서는 정수를 원소로 하는 집합의 연산 성능을 높이기 위한 비트 대응식 자료 구조 활용을 위하여 일반적인 원소 나열법과 성능 비교를 실험으로 측정하여 크게 개선되는 결과를 확인하였다.
• 이 논문은 회로 설계 시 필요한 회로 최소화 알고리즘을 공부하는 과정에서 진행되었다. 보통 회로 최소화는 진리표에서 시작하는 까르노 맵을 사용하지만, 이 방법은 수작업으로 진행되므로 오류 가능성이 높고, 입력 변수의 수가 많아지면 다루기가 힘들어진다.

본문요약 정보가 도움이 되었나요? 예 아니오 제출

이 논문을 인용한 문헌

더보기