하모닉 수(조화수, Harmonic number)

무한 급수를 공부하는 과정에서 혹은 알고리즘을 공부하는 과정에서 조화수(harmonic number)라는 개념을 자주 맞닥드리게 됩니다. 마주칠 때 마다 혼동될 수 있는 조화수에 대해서 왜 발산하는지와 근사 값은 어떻게 유도되는지 간단히 포스팅을 진행해보도록 하겠습니다.

 

조화수 정의(Harmonic number definition)

먼저 하모닉 수에 대한 정의를 말씀드리겠습니다. 정의는 다음과 같습니다.

$$ H_n = \sum_{i = 1}^{n} \frac{1}{i} = 1 + \frac{1}{2} + \frac{1}{3} + ... + \frac{1}{n}$$

 

정의는 아주 간단한데요 n에따라서 하모닉 수의 근사값은 대략 다음 정도로 구할 수 있습니다.

$$ n $$	$$ H_n $$
1	1
2	1.5
3	1.8333
4	2.0833
5	2.2833
6	2.45
7	2.5929
8	2.7179
9	2.8290
10	2.9290

그렇다면 n이 무한히 커지게 된다면 어떻게 될까요?

아마 흔히 발산한다고 배우셨을것 같은데 이에 대한 자세한 성질을 다음 내용에서 살펴보도록 하겠습니다.

 

조화수 발산

우선, 고등학교 수학에서 배우는 과정으로는 지금 식으로 아주 간단히 조화수가 발산함에 대한 증명이 가능합니다.

$$ \lim_{n \to \infty} H_n = 1 + \frac{1}{2} + \frac{1}{3} + \frac{1}{4} + \frac{1}{5} + \frac{1}{6} + \frac{1}{7} + \frac{1}{8} + \frac{1}{9} + ... $$

$$ \geq 1 + \frac{1}{2} + \frac{1}{4} + \frac{1}{4} + \frac{1}{8} + \frac{1}{8} + \frac{1}{8} + \frac{1}{8} + \frac{1}{16} + ... $$

$$ = 1 + \frac{1}{2} + \frac{1}{2} + \frac{1}{2} + ... = \infty$$

 

이번에는 정적분의 성질을 통하여 하모닉 수가 발산함을 살펴보도록 하겠습니다.

붉은색 영역의 넓이가 \(H_{n}\)에 해당한다고 볼 수 있는데요, 여기서 그래프는 \(y = \frac{1}{x}\) 이고, 이 그래프의 정적분 영역과 넓이를 비교해보도록 하겠습니다.

주황색 영역은 정적분 \(\int_{1}^{n} \frac{1}{x} dx = ln(n)\) 에 해당합니다.

여기서 보실 수 있는 것은 붉은색 영역 넓이가 주황색 영역 넓이보다 항상 크거나 같을 수 밖에 없다는 것입니다. 직관적으로 쉽게 이해되시나요? 즉, \(\int_{1}^{n} \frac{1}{x} dx = ln(n) \leq H_{n}\) 이고,

n이 무한히 커지면 \(\lim_{n \to \infty} ln(n) = \infty \) 이므로, \(\lim_{n \to \infty} H(n) = \infty \)도 성립할 수 밖에 없는 것이 보여지지요.

 

조화수와 로그함수의 관계

위의 그래프 관계로 보아 조화수와 로그함수 간의 밀접한 관계가 있는 것은 분명해 보입니다. 물론 더 타이트한 바운드를 증명해볼 수도 있고 깊은 성질에 대해 탐구해볼 수도 있겠지만, 여기서는 아주 직관적으로 살펴볼 수 있는 간단한 관계에 대해서만 다루어보겠습니다.

푸른색 영역은 \(H_{n} - 1\)에 해당하는 것을 확인해보실 수 있습니다. 붉은 색 영역을 왼쪽으로 1씩 움직인 뒤, 가장 긴 바를 제거해주면 똑같은 상태가 됩니다.

이 영역은 주황색 영역보다는 분명히 넓이가 작다는 것을 확인해보실 수 있습니다.

 

즉, 푸른색 영역 넓이 \(\leq \) 주황색 영역 넓이 \(\leq \) 붉은색 영역 넓이가 성립하는 관계를 쉽게 체크할 수 있습니다.

 

따라서,

$$ H_{n} - 1 \leq ln(n) \leq H_{n} $$

의 관계로 \(H_{n}\) 과 \(ln(n)\)의 관계를 간단히 살펴보았습니다.

컴퓨터 공학에서는 조화수가 등장하면 \(O(log(n))\)의 복잡도로 설명할 수 있는 이유가 다음과 같은 이유라고 이해해주시면 좋을 것 같습니다. 조화수가 가지고 있는 더 복잡한 성질도 많고 바운드에 대해서도 더 깊게 다루어볼 수 있지만 이번 포스팅에서는 이정도로 조화수의 기본적인 성질을 살펴보는 것으로 마무리하도록 하겠습니다.