Skip to content

調和級数的計算量

概要

下記のようなループの計算量は \(O(N \log N)\) となる。(エラトステネスの篩や倍数の列挙など)

for i in range(N):
    for j in range(i, N, i):
        # 何らかの処理

これは N が十分大きい時に下記のようにして求められる。

\[\begin{split} \frac{N}{1} + \frac{N}{2} + \frac{N}{3} + ... + \frac{N}{N} &= N(\frac{1}{1} + \frac{1}{2} + \frac{1}{3} + ... + \frac{1}{N}) \\ & \fallingdotseq N\int_{1}^{N}\frac{1}{x}{dx} \\ &= N \log{N} \end{split}\]

参考