algorithm - T（n）= T（n-1）+ 1/nの漸近的複雑さ

Question

時間計算量のあるアルゴリズムがあります

    T(n)=T(n-1)+1/n if n>1
        =1          otherwise

私はその漸近的な複雑さを解き、順序を「n」として取得していますが、与えられた答えは「logn」です。それが正しいか？log nの場合、なぜですか？

Answer 1

T（n）が1からnまでのkの値の1 / kの合計であることが簡単にわかります（または誘導によって正式に証明されます）。これはn番目の調和数であり、H _n = 1 + 1/2 + 1/3 + ... + 1/nです。

漸近的に、調和数はlog（n）のオーダーで増加します。これは、合計の値が1からnまでの1 / xの積分に近いためです。これは、nの自然対数に等しくなります。実際、H _n = ln（n）+γ+ O（1 / n）ここで、γは定数です。このことから、T（n）=Θ（log（n））であることを簡単に示すことができます。

Answer 2

詳細については：

とH(N) = 1 + 1/2 + 1/3 + ... + 1/N

関数x :-> 1/xは減少関数なので：

左の部分から合計し1 to N、右の部分から合計し2 to Nて加算すると1、次のようになります。

次に、左右の部分を計算します。ln(N+1) <= H(N) <= 1 + ln(N)

H(N)/ln(N) -> 1したがって、これはH(N)=Θ(log(N))

（http://fr.wikipedia.org/wiki/S%C3%A9rie_harmonique#.C3.89quivalent_de_Hnから）