algorithm - T(n)=T(n-1)+1/n的渐近复杂度

Question

有一种算法具有时间复杂度

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

我正在解决它的渐近复杂性，并将顺序设为“n”，但给出的答案是“log n”。这是对的吗？如果是log n，那为什么？

score 9 · Accepted Answer

很容易看出（或用归纳法正式证明）T(n) 是从 1 到 n 的 k 值的 1/k 之和。这是第n次谐波数，H _n = 1 + 1/2 + 1/3 + ... + 1/n。

渐近地，谐波数在 log(n) 的数量级上增长。这是因为该和的值接近于 1/x 从 1 到 n 的积分，它等于 n 的自然对数。事实上，H _n = ln(n) + γ + O(1/n) 其中 γ 是一个常数。由此，很容易证明 T(n) = Θ(log(n))。

score 3 · Accepted Answer

更多细节：

和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))

2 回答 2