inamori https://blog.hatena.ne.jp/inamori/ inamori’s diary https://inamori.hateblo.jp/ アルゴリズム 次の関数について考えます。 これをそのまま書くと、kはnまでで十分だから、 def H(n): return sum(n / k for k in xrange(1, n + 1)) ですね。O(n)の計算量のはずです（nが小さければ）。 さて、この計算を速くできないでしょうか。まず、n = 10で具体的な計算をしてみましょう。 H(n) = 10/1 + 10/2 + 10/3 + 10/4 + 10/5 + 10/6 + 10/7 + 10/8 + 10/9 + 10/10 = 10 + 5 + 3 + 2 + 2 + 1 + 1 + 1 + 1 + 1 です。最後のほう、1が続きますよね… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Finamori.hateblo.jp%2Fentry%2F20120708%2Fp1" title="上下で計算法を変える - inamori’s diary" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> Hatena Blog https://hatena.blog 2012-07-08 00:00:00 rich https://inamori.hateblo.jp/entry/20120708/p1 1.0 100%