메모리 적응 형 병합 알고리즘?

Question

많은 알고리즘은 merge algorithm을 사용하여 두 개의 서로 다른 정렬 된 배열을 단일 정렬 된 배열로 병합합니다. 예를 들어, 어레이

1 3 4 5 8 

및

2 6 7 9 

이러한 배열의 병합

1 2 3 4 5 6 7 8 9 

전통적으로 병합하는 두 가지 방법이있을 것 어레이를 것 입력으로서 주어진 정렬 된 배열 (연결된 목록을 병합하는 경우는 매우 다르다는 점에 유의하십시오). 첫째, 저장소에 임시 버퍼를 할당 한 다음 병합 결과를 임시 버퍼에 저장하여 작동하는 out-of-place 병합 알고리즘이 있습니다. 둘째, 두 배열이 같은 입력 배열의 일부인 경우 O (1) 보조 저장 공간 만 사용하고 두 개의 인접한 시퀀스를 하나의 정렬 된 시퀀스로 다시 배열하는 in-place merge algorithms이 있습니다. 이 두 가지 클래스의 알고리즘은 모두 O (n) 시간에 실행되지만 out-of-place 병합 알고리즘은 이러한 엄격한 메모리 요구 사항이 없으므로 훨씬 더 낮은 상수 계수를 갖는 경향이 있습니다.

제 질문은이 두 접근법을 "보간"할 수있는 알려진 병합 알고리즘이 있는지 여부입니다. 즉 알고리즘은 O (1)과 O (n) 메모리 사이의 어느 곳에서나 사용할 수 있지만 사용 가능한 메모리가 많을수록 더 빠르게 실행됩니다. 예를 들어, 알고리즘에 의해 수행 된 배열 읽기/쓰기의 절대 개수를 측정하려면 ng (s) + f (s) 형식의 런타임이있을 수 있습니다. 여기서 s는 사용할 수있는 공간 크기이고 g (s)와 f (s)는 이용 가능한 공간의 양으로부터 유도 할 수있는 함수이다. 이 함수의 장점은 주어진 메모리 제약 조건에서 가능한 한 가장 효율적인 방법으로 두 배열을 병합하려고 시도 할 수 있다는 것입니다. 시스템에서 사용할 수있는 메모리가 많을수록 메모리가 더 많이 사용되고 성능은 더 좋습니다 (이상적으로). .

더 정식으로 알고리즘은 다음과 같이 작동해야합니다. 입력으로 인접한 두 개의 정렬 된 범위로 구성된 배열 A가 주어진다면 배열의 요소를 배열 순서대로 정렬해야합니다. 알고리즘은 외부 공간을 사용할 수 있으며 모든 경우에 최악의 경우 O (n)이어야하지만 사용하기에 더 많은 양의 보조 공간이 주어지면 점진적으로 더 빠르게 실행해야합니다.

는 이런 종류의 알고리즘에 익숙한 사람이 (또는 하나의 설명을 찾아 볼 위치를 알아?)

가 가

Answer 1

는 "자사의 런타임 복잡성 따라 적어도 문서에 따르면, in-place merge function in SGI STL 적응하고 얼마나 많은 메모리를 사용할 수 있는가? " 물론 소스 코드를 확인해 볼 수 있습니다.

Answer 2

EDIT : STL은 inplace_merge이며 사용 가능한 임시 버퍼의 크기에 맞춰 조정됩니다. 임시 버퍼가 적어도 하위 배열 중 하나만큼 큰 경우 O (N)입니다. 그렇지 않으면 병합을 두 개의 하위 병합과 반복으로 나눕니다. 분할은 O (log N)을 사용하여 회전 할 다른 하위 배열의 오른쪽 부분을 찾습니다 (2 진 검색).

따라서 사용 가능한 메모리 양에 따라 O (N)에서 O (N log N)로 변경됩니다. 링크에 대한 감사 agksmehx-