Recursive Definition of the SymMerge Algorithm
Pok‐Son Kim · Journal of Korean institute of intelligent systems · 2017
병합 알고리즘은 원소의 개수가 과 인 두 개의 배열된 인접수열을 원소의 개수가 인 배열된 하나의 수열로 만드는 알고리즘이다. 우리는 SymMerge라고 명명한 스테이블하고, 비트의 메모리를 추가적으로 필요로 하는 병합알고리즘을 소개하였고 비교횟수 그리고 덮어쓰기 (assignment)와 관련해 최악의 경우에 대한 복잡도 분석을 소개했다. 그리고 기존의 논문에서 우리는 SymMerge 알고리즘의 정의를 유사부호 (Pseudocode)를 이용해 묘사하였다.BR 이 논문에서 우리는 -재귀함수를 이용해 SymMerge 알고리즘이 정의 될 수 있음을 보이고자 한다. 추가로 이러한 재귀적 정의를 바탕으로 원소의 개수가 과 인 두 개의 입력수열을 병합하기 위해 요구되는 비교횟수가 재귀 함수에 의해 계산될 수 있음을 보인다.