max, min 동시에 찾기 / 두 번째로 큰 값 찾기

min, max 모두 찾을 때 조금 더 효율적인 방법

배열에서 최댓값과 최솟값을 모두 찾는 단순하고 일반적인 방법은 최대키, 최소키를 각각 찾는 방법이다. 이런 방식은 최대키를 찾는데 \(n-1\)번 비교, 최소키를 찾는 문제도 이와 같으므로 총 \(2n-2\)번 비교하게 된다.

다음과 같은 방법을 사용하면 최댓값과 최솟값을 모두 찾는데 \(3\lfloor{n/2}\rfloor\)번만 비교할 수 있다. 입력 원소의 각 쌍에 대해 먼저 둘을 비교한 다음, 큰 쪽을 max와 비교하고 작은 쪽을 min과 비교한다. 이렇게 되면 (max, x1), (max, x2), (min, x1), (min, x2) 4번 비교해야 하는 것을 (x1 , x2), (max, x1), (min, x2)3번으로 줄일 수 있다. ( x1 > x2인 경우)

하한선

모든 키가 서로 다르다고 가정할 때, 키 x = max이고 키 y = min임을 보이기 위해서는 x를 제외한 다른 모든 키들은 어떤 비교에서 패배한 적이 있고, y를 제외한 다른 모든 키들은 어떤 비교에서 승리한 적이 있어야 한다. 즉, 각 승리와 패배를 1 단위의 정보라고 한다면, 최댓값과 최솟값을 확신하기 위해서는 승리와 패배가 각각 \(n-1\)개 씩 필요하므로 \(2n-2\) 단위의 정보가 필요하다.

(max, x1) 따위의 비교는, 배열의 원소 하나가 승리 또는 패배하게 되므로 1 단위의 정보 밖에 얻지 못한다. 반면 (x1 , x2) 비교는 배열의 원소 두 개의 승리 또는 패배가 결정되므로 2 단위의 정보를 얻을 수 있다.

알고리즘이 2 단위의 정보를 얻을 수 있는 경우는 두 키 모두 한 번도 비교되지 않은 경우이고 두 쌍씩 짝지으면 \(n/2\)쌍이 나오므로 비교 횟수는 \(n/2\)번, 획득한 단위 정보는 \(n\)이다. 이외의 비교에서는 한 번에 최대 1 단위의 정보밖에 획득할 수 없다. 최댓값과 최솟값을 확신하기 위해서는 \(n-2\) 단위의 정보가 추가로 필요하므로, \(n-2\)번의 비교가 추가로 필요하다. 따라서 최소한 \(n/2 + n-2 = 3n/2 -2\) 회의 비교가 필요하므로 Optimal하다.

두 번째로 큰 값 찾기 : 승자 트리

둘씩 짝지어 토너먼트 돌려 이진 트리를 구성한다. (아래에서 위로)

secondLargest = x4 || x5 || x7이다. (각 depth마다 1개씩 나온다. = \(\lg{n}\)개) 최악의 경우 비교 횟수는

• 승자 트리 만드는데 \(n-1\)번 비교
• \(\lg{n}\)개에서 max찾는데 \(\lg{n} - 1\)번 비교 이 방법으로 max와 secondLargest를 최악의 경우 총 \(n + \lceil \lg{n} \rceil - 2 \)번의 비교로 찾을 수 있으며 Optimal하다. 하한선에 대한 증명은 상대자 논증을 이용할 수 있다.

이 방법 안쓰고 무식하게 찾으면 2n-3번 비교해야 함.

공간 절약

토너먼트는 완전 이진 트리로 구성할 수 있기 때문에 heap을 사용할 수 있다. \(n\)개의 원소에 대한 트리는 \(2n-1\)개의 노드로 구성되기 때문에, E[1] ~ E[2\*n-1]배열 잡고 \(n\)개의 원소를 c E[n] ~ E[2\*n-1] 위치에 둔 다음 토너먼트 결과를 뒤에서부터 채워 나가면 선형 공간 안에서 해결할 수 있다.