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

 

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

배열에서 최댓값과 최솟값을 모두 찾는 단순하고 일반적인 방법은 최대키, 최소키를 각각 찾는 방법이다.

이런 방식은 최대키를 찾는데 \\(n-1\\)번 비교, 최소키를 찾는 문제도 이와 같으므로 총 \\(2n-2\\)번 비교하게 된다.

 

다음과 같은 방법을 사용하면 최댓값과 최솟값을 모두 찾는데 \\(3\lfloor{n/2}\rfloor\\)번만 비교할 수 있다.

입력 원소의 각 쌍에 대해 먼저 둘을 비교한 다음, 큰 쪽을 `` max``와 비교하고 작은 쪽을 `` min``과 비교한다.

이렇게 되면

``c (max, x1), (max, x2), (min, x1), (min, x2)`` 4번 비교해야 하는 것을

``c (x1 , x2), (max, x1), (min, x2)`` 3번으로 줄일 수 있다. (`` x1 > x2``인 경우)

 

하한선

모든 키가 서로 다르다고 가정할 때,

키 `` x = max``이고 키 `` y = min``임을 보이기 위해서는 `` x``를 제외한 다른 모든 키들은 어떤 비교에서 패배한 적이 있고, `` y``를 제외한 다른 모든 키들은 어떤 비교에서 승리한 적이 있어야 한다.

즉, 각 승리와 패배를 1 단위의 정보라고 한다면, 최댓값과 최솟값을 확신하기 위해서는 승리와 패배가 각각 \\(n-1\\)개 씩 필요하므로 \\(2n-2\\) 단위의 정보가 필요하다.

 

``c (max, x1)`` 따위의 비교는, 배열의 원소 하나가 승리 또는 패배하게 되므로 1 단위의 정보 밖에 얻지 못한다.

반면 ``c (x1 , x2)`` 비교는 배열의 원소 두 개의 승리 또는 패배가 결정되므로 2 단위의 정보를 얻을 수 있다.

 

알고리즘이 2 단위의 정보를 얻을 수 있는 경우는 두 키 모두 한 번도 비교되지 않은 경우이고 두 쌍씩 짝지으면 \\(n/2\\)쌍이 나오므로 비교 횟수는 \\(n/2\\)번, 획득한 단위 정보는 \\(n\\)이다.

이외의 비교에서는 한 번에 최대 1 단위의 정보밖에 획득할 수 없다.

최댓값과 최솟값을 확신하기 위해서는 \\(n-2\\) 단위의 정보가 추가로 필요하므로, \\(n-2\\)번의 비교가 추가로 필요하다.

따라서 최소한 \\(n/2 + n-2 = 3n/2 -2\\) 회의 비교가 필요하므로 Optimal하다.

 

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

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

``c 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\\)개의 노드로 구성되기 때문에, 

``c E[1] ~ E[2*n-1]`` 배열 잡고 \\(n\\)개의 원소를 ``c E[n] ~ E[2*n-1]`` 위치에 둔 다음 토너먼트 결과를 뒤에서부터 채워 나가면 선형 공간 안에서 해결할 수 있다.