k 목록을 병합하는 가장 좋은 방법은 무엇입니까?

Question

O (s1 + s2) 시간에 s1과 s2 크기의 두리스트 L1과 L2를 병합 (합집합을 찾습니다)하는 병합 함수가 있다고 가정하십시오. 크기 s1, s2, ..., sk의 k 목록을 병합하는 최적의 방법은 무엇입니까?

처음에는 s1, ..., sk를 정렬하고 가장 낮은 두 크기에 해당하는 처음 두 목록을 정렬해야한다고 생각합니다. 이들이 합쳐지면 정렬 된 크기 목록에서 크기의 위치를 ​​찾아 하나의 목록으로 끝날 때까지 프로세스를 계속 진행합니다.

나는 두 가지 문제가 있습니다. 1. 이것이 실제로 최적인지 (더 빠른 시간에 다시 나타날 다른 방법이 있습니까)? 2. 병합 할 때 목록 크기가 변경되는 경우 실행 시간을 어떻게 분석합니까?

Answer 1

이 이다 정확하게 알려진 주파수 s1, s2, … sk와 k 심볼들의 알파벳으로 이루어지는 문자열을위한 최적의 가변 길이 부호화 비트를 찾는 것과 같은 문제. 귀하의 알고리즘은 정확하게 Huffman algorithm이며 알고리즘 (및 많은 온라인 리소스)에 대한 모든 교과서에서 최적의 증거를 찾을 수 있습니다. 그 이유는 단순한 정확성 증명이있는 욕심 많은 알고리즘의 전형적인 사례이기 때문입니다.

양방향 병합을 반복적으로 적용하면 각 노드가 병합되는 이진 트리가 생성됩니다. 트리가 주어지면 전체 병합의 총 비용에 대한 리프의 영향은 해당 리프의 무게에 트리의 깊이가 곱해진 값입니다. (각 노드는 병합되며 리프의 값은 리프에서 루트까지의 경로에있는 머지에 정확히 참여하며, 이러한 머지의 수는 트리의 리프 깊이입니다.) 비슷하게 또는 동일하게 - -, 허프만 인코딩 비트 스트링의 전체 길이는 심볼의 가중치 (빈도)와 구조 트리의 해당 심볼에 해당하는 잎의 깊이의 곱의 합입니다.

알고리즘 (호프만 트리 빌더 작성자가 자주 놓치지 않는)에 대한 한 가지 작은 개선 사항 : 가중치를 정렬해야하지만 s1, s2, … sk 만 필요합니다. 거기에서 알고리즘은 항상 두 개의 가장 낮은 노드를 선택하여 추가합니다. 결과 합은 크기가 단조롭게 감소하지 않아야합니다 (이전 합계보다 작 으면 이전 합계는 두 개의 가장 작은 요소 합계가 될 수 없습니다). 따라서 합계를 대기열에 넣을 수 있습니다. 각 단계에서 나뭇잎의 정렬 된 배열 또는 노드의 (암시 적으로) 정렬 된 큐에서 두 개의 가장 작은 요소를 선택합니다.

잎 배열에 노드 대기열을 덮어 쓰면이 작업을 더욱 최적화 할 수 있습니다. 큐는 어레이의 맨 아래에서 맨 위로 커지기 때문에 큐의 맨 위가 배열의 맨 아래를 따라 잡을 수 없음을 증명하는 것은 매우 간단합니다.