調和級数の order について

更新日時:

目的

この記事は、正の整数 $N$ に対して \[ \sum _ {j = 1} ^ N \frac{N}{j} = O(N \log N) \tag{1} \] であることを証明するものです。 AtCoder などのプログラミングコンテスト出場者の方に対して書きます。

この級数はプログラミングコンテストの計算量を見積もる際に山ほど出てきます。 AtCoder でも解説放送でこれが出る度に、 snuke さんが説明し、 rng さんが自分で調べてくださいという。コメントを見ると、証明が気になる人もいるようです。この記事で証明したいと思います。

これは高校 3 年生の積分の知識があれば証明はできますが、その証明を書くのは意外と難しいかもしれません。この理由は、高校の数学は「評価」という概念にほとんど触れることがないからです。その辺も含めて解説を試みたいと思います。

高校 3 年生までの数学がわかっている人向けに書きます。一方で大学以降の数学がきちんとわかっていればこんなのは一撃です。近くにいる数学わかっている人にお聞きになるとすぐに答えてくれるでしょう。ゆえにこれは「大学数学の心構え入門」みたいな記事です。一部では説教臭い言い方をします。不快に思ったらすみません。けど、高校までの何も知らない私に聞かせてやりたい言葉です。ゆえにそのまま載せます。

前提知識

まず (1) 式は \[ \sum _ {j = 1} ^ N \frac{1}{j} = O(\log N) \tag{2} \] と同値です。以下では (2) 式を証明することにします。

証明の際に次の定理を使います。以下では単に定理と言います。

定理:正の整数を定義域として実数を返す関数 $f, g _ 1, g _ 2$ に対し、任意の正の整数 $N$ に対し、 \[ g _ 1(N) \leq f(N) \leq g _ 2(N) \tag{X.1} \] が成立しているとする。また、ある正の整数を定義域として実数を返す関数 $h$ が存在し、 \[ g _ 1 (N) = O(h(N)), \ \ \ \ g _ 2(N) = O(h(N)) \tag{X.2} \] が成立するものとする。このとき、次式が成立する。 \[ f(N) = O(h(N)). \tag{3} \]

これは実は $O$ 記法の厳密な定義と照らし合わせると少しよくないのですが、この記事を読む方は全く気にしなくていいです1

(2) と (3) を見比べると、どうにかして \[ \begin{align} f(N) &= \sum _ {j = 1} ^ N \frac{1}{j}, \\\ h(N) &= \log N \end{align} \] となるように定理を適用できれば、我々は (2) 式を証明することができます。

そこで以下の方針としては、 (X.1) 式と (X.2) 式を充たすような $g _ 1, g _ 2$ を発見、または、構成すれば良い とわかります。

評価について

正式な定義ではありませんが、 (X.1) 式のような不等式を「 $f$ の評価」と言います。もっというと、与えられた $f$ に対して (X.1) を充たすような $g _ 1, g _ 2$ を見出すことを「 $f$ を評価する」と表現します。 $g _ 1$ を見出すことを「下から評価する」といい、 $g _ 2$ を見出すことを「上から評価する」といいます。

これは高校の数学ではほとんど出てこない考え方です。正確な言い方をすると、高校の教科書の中で可能な限り隠蔽されている概念です。しかし、大学 1 年生になると突然重要になる概念です。

一応高校 3 年生でも「はさみうちの原理」というものを習います。上の定理は、ほとんど、それに近い定理、私の感覚ではほぼ同じようなものです。

ここで重要なのが、いかにして「意味のある」 $g _ 1, g _ 2$ を得るのかということです。例えばの話、 \[ 0 \leq f(N) = \sum _ {j = 1} ^ N \frac{1}{j} \leq \sum _{j = 1}^N 1 = N \tag{4} \] は絶対に成り立っています。つまり $g _ 1 (N) = 0$ とし、 $g _ 2 (N) = N$ とすれば (X.1) 式は充たされます。

これは確かに $f$ の評価です。しかしこれは全然、全く、何の役にも立たない、意味のない評価です。ここでいう「意味のない」は、私がそう感じているということではありません。今回の文脈で「意味がある」の正確な意味するところは (X.2) 式です。 (X.2) 式が成り立たないなら、 (X.1) 式を充たしていたとしても、その $g _ 1, g _ 2$ には今回は用がないということです。そこには限界があります。逆に言えば、(X.1) と (X.2) 式を充たせば、どのような $g _ 1, g _ 2$ でも定理を適用できます。そこには自由度があります。

評価をするときには、限界と自由度がある。これが重要です。 普通の数学という視点から考えると、高校の数学では、不等式の等号条件を気にしすぎです。例えば (4) 式において私は $\leq$ を使いました。しかし、正の整数 $N$ に対して、どちらの $=$ も成り立ちません。だから $\leq$ のところは、もしかしたら読者は $<$ でないとモヤモヤするかもしれません。しかしそれは、普通の数学をやる上では、よくないモヤモヤです。もちろんお好きであれば $<$ と書いてくださっても良いです。しかし、 今の我々の目的は、定理を使って (2) 式を証明することであって、「ベストの」不等式を追求することではありません。 ですから、どちらでもいいのです。この「自由度」の話は下でまたします。

具体的な評価

この記事は深夜に書いていて、 gnuplot とかでグラフかくのめんどいので手描きでかきます。

まず $f(N) = \sum _ {j = 1} ^ N 1/j$ の値は、図 1 の長方形の面積の和に等しいです。

図 1

これは特に何の知識もなく、中学生でもわかると思います。横の長さが $1$ で、縦の長さが $1/j$ の長方形の面積を $j = 1, \dots, N$ まで足したものです。

次は定積分の知識を使います。図 2 を見ればわかる通り、 $G _ 1 (x) = 1/x$ とすると、 \[ g _ 1 (N) = \int _ 1 ^ {N + 1} G _ 1 (x) dx \leq f(N) = \sum _ {j = 1} ^ N \frac{1}{j} \tag{Y.1} \] が成立します。わからない人は高校の数学 III の教科書参照。「図で説明するなんてずるい」ですって? そう思う人は次節の補足を読んでください。ともかく、これで下からの評価が得られました。

図 2

また、図 3 を見ればわかる通り、 $G _ 2 (x) = 1/(x - 1)$ とすると、 \[ f(N) = \sum _ {j = 1} ^ N \frac{1}{j} \leq g _ 2 (N) = 1 + \int _ 2 ^ {N + 1} G _ 2 (x) dx \tag{Y.2} \] が成立します。最初の長方形だけ $1 + $ として処理していることに注意してください。これで上からの評価も得られました。

図 3

補足:数式で示す方法

上の説明は、別に図で理解できれば十分です。しかし例えば大学の教員が学生に「式で示してください」と言った時に答えられないとそれはそれでよくないなと思うので、説明します。

まず上と下の評価は別々にやるのがコツです。上の図を踏まえて、一つ一つの長方形について評価を与えればいいだけです。

下からの評価は次のようにします。 $1 \leq j \leq N$ は整数とします。このとき、実数 $j \leq x \leq j + 1$ に対して \[ \frac{1}{x} \leq \frac{1}{j} \] が成立します。したがってこれを区間 $[j, j + 1]$ で積分して \[ \int _ j ^ {j + 1} \frac{1}{x} dx \leq \int _ j ^ {j + 1} \frac{1}{j} dx = \frac{1}{j} \] が得られます。これを $j = 1, \dots, N$ で両辺和を取ることにより (Y.1) が得られます。

上からの評価も同様です。 $2 \leq j \leq N$ は整数とします。このとき、実数 $j \leq x \leq j + 1$ に対して \[ \frac{1}{j} \leq \frac{1}{x - 1} \] が成立します。したがってこれを区間 $[j, j + 1]$ で積分して \[ \frac{1}{j} = \int _ j ^ {j + 1} \frac{1}{j} dx \leq \int _ j ^ {j + 1} \frac{1}{x - 1} dx \] が得られます。これを $j = 2, \dots, N$ で両辺和を取り、さらに両辺に $1$ を足すことにより (Y.2) が得られます。

最後の詰め

あとは定積分を原始関数を使って計算をするだけです。 \[ \begin{align} g _ 1 (x) &= \int _ 1 ^ {N + 1} \frac{1}{x} dx = \Big[ \log x \Big] _ 1 ^{N + 1} = \log (N + 1), \\\ g _ 2 (x) &= 1 + \int _ 2 ^ {N + 1} \frac{1}{x - 1} dx = 1 + \Big[ \log (x - 1) \Big] _ 2 ^{N + 1} = 1 + \log N \end{align} \] で、 $g _ 1, g _ 2$ とも $O(\log N)$ であることがわかります。つまり (X.1), (X.2) が成立します。これで定理が適用できて、 (2) 式が得られました。ゆえに (1) 式が得られました。証明終わりです。

後日談(?)

以上で十分です。しかし、「注意深い」人はこういうかもしれません。「 $\log(N + 1)$ も $1 + \log N$ も、本当に $O(\log N)$ なのか」と。または「上の『定理』を証明してみろ」と。

これは、証明しろと言われたら、定義に立ち戻って証明できないといけないでしょう。しかも簡単です。それは事実です。けど、正直私はナンセンスな質問に思えて仕方がありません。この記事ではあえて書かないことにします。この疑問に苛まれている方は、自分で $O$ 記法を定義を調べて自分で考えてください。

その理由:この質問がナンセンスであるのは「評価」という「概念」と相容れない疑問だからです。質問がよくないです。

先ほど評価の限界と自由度について話しました。特に自由度については重要です。例えば私が手を滑らせて、 \[ \begin{align} g _ 1 (x) &= \frac{1}{1992}\log(N + 1) - 725, \\\ g _ 2 (x) &= 1992 \log N + 7 e^{-N} + 25 \end{align} \] と評価しても、 (X.1), (X.2) が成立しますので、定理を示す上では支障がありません2。これは極端で馬鹿げた例ですが、しかし重要なことを示唆しています。 $g _ 1, g _ 2$ については、最終的に、定数 $C _ 1 > 0$, $C _ 2$ が存在し、 \[ C _ 1 \log N + C _ 2 \] の形に評価できれば、 $C _ 1, C _ 2$ は何でもいいのです。本当に何でもいいのです。だから、 評価において、証明をつける際には、定数部分はどんどん上に、または下の値に取り替えていくことが重要 です。この思想が端的に現れているのが、 (Y.2) で $1$ を別に寄せたところです。わかりやすく言えば、定数部分を無視したのです。議論を簡潔にするために。

繰り返しますが、 $C _ 1, C _ 2$ は何でもいいのです( $C _ 1 > 0$ であれば)。ゆえに、アルゴリズムの世界ではまず最初に「時間計算量の $O$ が…」と議論が始まり、その次に「定数部分が…」という表現をするわけです。

先ほどのような疑問を他人に「ふっかける」人は、何のためにアルゴリズムの計算量の記述に $O$ 記法が導入されているのか、反省するべきです。これはデータ処理量である $N$ が大きくなった時に、計算量に対し、何が支配的になるのかを明らかにするために導入されているものです。つまり、定数部分である $C _ 1 > 0$ と $C _ 2$ の部分を捨象することにより、より良い理解、普遍的な理解に達しようというものです。そのことを忘れてはいけない。「 $\log(N + 1)$ も $1 + \log N$ も $O(\log N)$ であること」「上の『定理』」はどちらも、捨象された部分に相当します。だからこういう議論を他人にふっかけるのはいいことではありません。大事なことを見るために、力点を置くべきところに注力することが重要だと私は思います。

  1. (この記事の読者ではない人向け:混乱するくらいなら読まない方がいい) 正確さのために書いておきます。大前提としてこれは $N \to \infty$ の漸近挙動について記述しています。また、この定理は実は下からの評価が不要です。つまり $g _ 1$ の条件はなくて正しいです。これは $O$ 記法は本来上界を定める記法だからです。今回は下からの評価もしているので、次のように読み替えていただけるとより強い主張を証明しているとわかります。すなわち (X.2) 式は $g _ 1 (N) = \Omega(h(N)), g _ 2(N) = O(h(N))$ であり、結論の (3) 式は $f(N) = \Theta(h(N))$ であると読み換えるとよろしいです。以下の証明部分で、 $g _ 1 (N) = \log (N + 1) = \Omega(\log N)$ は成立していますので、この記事では実は $f(N) = \Theta( \log N )$ を証明していることになります。 

  2. どうでもいいですけど 1992 年 7 月 25 日は『STEINS;GATE』シリーズに登場する牧瀬紅莉栖さんの誕生日です。私も同じ誕生日です。 3 年早く生まれていますけど。