xlogx 꼴의 합의 상한

프로그래밍 문제를 풀다 보면 a개의 정수들을 정렬하는 일이 굉장히 많은데, 이 a개의 정수들을 한꺼번에 정렬하는 것(이때의 시간복잡도는 \(O(a\log a)\))과, 정수들을 n개의 그룹으로 분할해서 각 그룹끼리만 n번 정렬하는 것 중에 어떤 것이 빠를지 궁금해졌다.

n=10일 때만 간단한 프로그램으로 확인해보니 대부분의 경우 항상 각 그룹을 정렬하는 것이 빠른 것을 확인할 수 있었다.

이 현상을 조금 더 일반화해서 다음과 같은 수학적인 가설을 세울 수 있었다.

양수 \(x_{1}, x_{2}, \cdots , x_{n}\)에 대해 \( x_{1}+x_{2}+\cdots+x_{n}=a\)일 때, \( x_{1} \log x_{1} +\cdots+x_{n} \log x_{n} < a \log a\)이다.

(로그의 밑은 중요하지 않다. 어차피 양변을 적당한 상수로 나누면 같아진다.)

 

우선 n=2일 때는 성립한다. 이때는 한 변수 x에 관한 식인 $$ x \log x + (a-x) \log (a-x) < a \log a \quad (0<x<a) $$로 나타낼 수 있는데, (위 가설에서 자유도는 n-1이다.) x에 관해 미분해보면 x=a/2일 때 최소였고, x가 0 또는 a로 갈수록 값이 \(a\log a\)로 접근해서 상한은 예상대로(?) \(a\log a\)였다. 다음은 a=10일 때 \(x \log x + (a-x) \log (a-x) - a \log a\)의 그래프를 그린 것이다. 항상 0보다 작은 것을 확인할 수 있다.

n=3일 때도 마찬가지다. 변수를 x, y, a-x-y로 놓고 다시 \(x \log x + y \log y + (a-x-y) \log (a-x-y) - a \log a\)의 그래프를 그려 보면,

대충 이렇게 0보다 작게 나온다. (엄밀한 확인은 안 해봤는데 그래프가 저 정도면...)

n=2일 때는 증명을 했고, n=3일 때도 대충 맞는 것으로 보아, 그렇다면 일반적인 n에 대해서도 성립하는 듯한데, 이걸 어떻게 증명할까? 수학적 귀납법을 사용하면 된다. 오랫동안 고민해온 문제 치고는 이걸 왜 생각을 못했나 싶다.

양수 \(x_{1},x_{2}\)에 대해서 다음이 성립함은 위에서 증명했다. (위 식을 조금만 변형하면 된다.)

$$x_{1}\log x_{1} + x_{2}\log x_{2} < (x_{1}+x_{2})\log (x_{1}+x_{2})$$

이제 \(n=k\)일 때 다음이 성립한다고 가정하자.

$$\sum _{i=1} ^{k} x_{i} \log x_{i} < (\sum _{i=1} ^{k} x_{i})\log (\sum _{i=1} ^{k} x_{i})$$

그러면 \(n=k+1\)일 때

$$\begin{align*}
\sum _{i=1} ^{k+1} x_{i} \log x_{i} &= \sum _{i=1} ^{k} x_{i} \log x_{i} + x_{k+1} \log x_{k+1} \\
&< (\sum _{i=1} ^{k} x_{i})\log (\sum _{i=1} ^{k} x_{i}) + x_{k+1} \log x_{k+1} \quad \textrm{(가정에 의해)} \\
&< (\sum _{i=1} ^{k} x_{i} + x_{k+1})\log (\sum _{i=1} ^{k} x_{i} + x_{k+1}) \quad \textrm{(2개짜리는 성립하므로)}\\
&= (\sum _{i=1} ^{k+1} x_{i})\log (\sum _{i=1} ^{k+1} x_{i})
\end{align*}$$

따라서 모든 \(n>2\)에 대해서도 성립한다.

상한은 모든 \(x_{i}\)들이 하나만 빼고 모두 0으로 접근할 때, \(a\log a\)이다.

 

아무튼 결론은, a개의 정수들을 한꺼번에 정렬하는 것보다, 정수들을 n개의 그룹으로 분할해서 각 그룹끼리만 n번 정렬하는 것이 더 빠르다.

 

식의 꼴이 \(x\log x\)일 때뿐만 아니라 \(x^{m}\) 등일 때도 증명이 가능하다. (코시-슈바르츠 부등식 증명도 이랬던 것 같은데...)