초록

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

본 논문에서는 기존의 정렬 알고리즘의 성능을 향상시키기 위하여 정보블록 전처리알고리즘(IBPA)이라는 전처리 알고리즘을 제안한다. IBPA는 정렬된 리스트(list)에 있는 데이터에 관한 정보를 생성하고, 생성된 정보를 이용하여 각 데이터를 재배치하며, 실제적인 정렬은 기존의 정렬 알고리즘을 그대로 이용하여 이루어진다. IBPA의 성능을 측정해본 결과, 2백만개의 랜덤데이터를 정렬한 경우, O(N2)의 평균시간복잡도를 갖는 정렬알고리즘의 0.003%, O(NlogN)의 평균시간복잡도를 갖는 정렬알고리즘의 52%, 그리고 O(N)의 평균시간복잡도를 갖는 정렬알고리즘의 89%정도의 비교회수만으로도 정렬할 수 있음을 보여주었다.

본 논문에서는 기존의 정렬 알고리즘의 성능을 향상시키기 위하여 정보블록 전처리알고리즘(IBPA)이라는 전처리 알고리즘을 제안한다. IBPA는 정렬된 리스트(list)에 있는 데이터에 관한 정보를 생성하고, 생성된 정보를 이용하여 각 데이터를 재배치하며, 실제적인 정렬은 기존의 정렬 알고리즘을 그대로 이용하여 이루어진다. IBPA의 성능을 측정해본 결과, 2백만개의 랜덤데이터를 정렬한 경우, O(N2)의 평균시간복잡도를 갖는 정렬알고리즘의 0.003%, O(NlogN)의 평균시간복잡도를 갖는 정렬알고리즘의 52%, 그리고 O(N)의 평균시간복잡도를 갖는 정렬알고리즘의 89%정도의 비교회수만으로도 정렬할 수 있음을 보여주었다.

AI 본문요약

엑셀 다운로드 AI-Helper

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

• 연구 주제
• 연구 방법
• 연구 결과

문제 정의

• 본 연구는 정렬 알고리즘의 성능을 개선시키는 방법에 관한 연구로서, 기존의 정렬 알고리즘은 변화시키지 않고, 다만 전처리 과정을 추가함으로써 기존의 。( ) 의 평균 시간복잡도를 갖는 정렬 알고리즘뿐만 아니라 (XNSgN)와(KN)의 평균시간복 잡도를 갖는 정렬 알고리즘의 성능을 개선하고자 한다. 전처리 과정은 정보 블록 전처리 알고리즘(IBPA; Information Block Preprocessing Algorithm)에 의해 수행되며, IBPA는 데이터의 분포 상태를 파악한 정보에 따라 정보 블록을 생성하고, 이 정보를 이용하여 데이터를 재배치하여, 각각의 블록을 기존의 정렬 알고리즘을 적용하여 최종 정렬을 수행함으로써 정렬 효과를 향상시키는 전처리 알고리즘을 말한다.
• 앞으로 연구해야 할 과제라고 할 수 있는 것은 크게 세 가지 호 볼 수 있다. 첫째, IBPA를 이용하여 기존의 정렬알고리즘보 다 빠른 새로운 정렬 알고리즘을 개발하는 것이다. 둘째, IBPA 의 성능을 좌우하는 요소가 블록 데이터 범위(BDR)와 정보 블록의 개수(M), 그리고 변수 p와 q이기 때문에, IBPA의 성능 향상을 위해서 이 네 가지 요소의 최적화에 대한 연구가 필수적이다.

제안 방법

• 2) 데이터의 종류 : 비교적 고른 분포를 보이는 난수 발생기 (random generator)로 생성된 랜덤 데이터로 실험하였다.
• 본 연구에서는 먼저 기존의 정렬 알고리즘의 종류와 성능을 살펴본 후, IBPA의 구조와 시간복잡도를 간략하게 분석하였다. IBPA의 실제적인 효과는 시간복잡도별로 몇 가지 정렬알고리 즘을 선정한 후 시뮬레이션을 통하여 확인하였으며, 실험결과 를 표와 그래프로 제시하였다.
• Part.3은 기존의 정렬 알고리즘을 이용하여 각각의 DB를 정렬하는 부분인데, (XN) 과 (X、N她N) 그리고 QA的의 평균 시간 복잡도를 갖는 정렬 알고리즘의 세 가지 경우로 나누어 기술하였다.
• 본 연구에서는 먼저 기존의 정렬 알고리즘의 종류와 성능을 살펴본 후, IBPA의 구조와 시간복잡도를 간략하게 분석하였다. IBPA의 실제적인 효과는 시간복잡도별로 몇 가지 정렬알고리 즘을 선정한 후 시뮬레이션을 통하여 확인하였으며, 실험결과 를 표와 그래프로 제시하였다.
• 둘째, IBPA 의 성능을 좌우하는 요소가 블록 데이터 범위(BDR)와 정보 블록의 개수(M), 그리고 변수 p와 q이기 때문에, IBPA의 성능 향상을 위해서 이 네 가지 요소의 최적화에 대한 연구가 필수적이다. 셋째, 본 연구에서 사용된 데이터 블록의 개념은 병렬처리 시스템(parallel processing system)에서 유용할 것으로 생각되므로 이에 적용하는 것이다.

대상 데이터

• 3) 데이터의 개수 : BDR이 50으로 설정된 상태에서 1, 000개를 측정단위로 하여 2백만 개 데이터까지 실험하였다. 그러나 삽입 정렬은은 O(A")의 평균 시간복잡도를 가지므로 데이터의 개수가 10만 개 이상일 때는 측정단위를 10만 개로 설정하여 실험하였다.
• 1) 정렬 알고리즘 : 삽입 정렬과 퀵 정렬[2][3] 그리고 기수 정렬 [3] 을 실험대상으로 선정하였다. 기수 정렬은 기수 교환 정렬 (radix exchange sort)로서, 32비트의 키(key)가 사용되었다.
• 3) 데이터의 개수 : BDR이 50으로 설정된 상태에서 1, 000개를 측정단위로 하여 2백만 개 데이터까지 실험하였다. 그러나 삽입 정렬은은 O(A")의 평균 시간복잡도를 가지므로 데이터의 개수가 10만 개 이상일 때는 측정단위를 10만 개로 설정하여 실험하였다.

성능/효과

• 4) 비교회수 : 'if'와 'while 그리고 'for'와 같은 명령문에서도 실제로는 비교가 발생하므로 정확한 비교회수를 측정하기 위해 이러한 명령문 역시 비교회수에 누적되었다.
• IBPA는 정렬 효과를 향상시키기 위한 새로운 전처리 알고리즘으로서, 성능 측정 결과 IBPA는 기존의 정렬 알고리즘이 가지는 평균 시간복잡도를 개선시키는 효과가 있음을 알 수 있었다.
• 결론적으로 2백만 개의 랜덤 데이터를 정렬한 경우를 기준으로 IBPA의 성능을 평가한다면, OQV) 의 평균 시간복잡도를 갖는 정렬 알고리즘의 0.003%, OCMbgAO의 평균시간복잡도를 갖는 정렬 알고리즘의 52%, 그리고 의 평균 시간복잡도를 갖는 정렬 알고리즘의 89%의 비교회수만으로도 정렬을 할 수 있음을 보여주었다. 따라서, IBPA의 효과는 OQW)의 평균시간복잡도 를 갖는 정렬 알고리즘의 경우에 가장 효과가 크다는 사실을 알 수 있다.
• 그리고 본 연구에 이용된 알고리즘 이외의 다른 정렬 알고리즘의 경우에서도 즉, 버블 정렬과 힙 정렬, 그리고 선택 정렬과 쉘 정렬에 있어서도 알고리즘 개선 효과를 확인할 수 있었다. 또한 이미 정렬된 데이터를 이용하여 실험한 경우에 있어서도 마찬가지 효과가 있었다.
• 둘째, 실험데이터가 랜덤 데이터이므로 데이터의 상태에 따라 시간복잡도가 달라지는 점을 감안해야하지만, 삽입 정렬에 IBPA를 적용했을 때 삽입 IB 정렬 알고리즘은 퀵 정렬과 대등한 정렬효과를 나타낸다는 것이다.
• 003%, OCMbgAO의 평균시간복잡도를 갖는 정렬 알고리즘의 52%, 그리고 의 평균 시간복잡도를 갖는 정렬 알고리즘의 89%의 비교회수만으로도 정렬을 할 수 있음을 보여주었다. 따라서, IBPA의 효과는 OQW)의 평균시간복잡도 를 갖는 정렬 알고리즘의 경우에 가장 효과가 크다는 사실을 알 수 있다.
• 첫째, IBPA가 적용된 경우 선형 시간(linear time) 알고리즘의 경우처럼 비교회수의 출력 선이 직선이 된다는 것이다. 이 사실은 시간복잡도의 기술 부분에서 언급한 변수 p는 N과 차이가 있음 올, 변수 q는 1보다 작은 수를 의미하는 것으로 해석될 수 있다.

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

이 논문을 인용한 문헌

더보기