和1 / i的渐近符号[关闭]

Question

什么是渐近符号

即

sum_(i = 1)^n (1 / i)

首先，这不是一个功课。其次，由于没有计算分数的公式，我不知道如何用n表达这个求和并得到渐近符号。

那可能是Theta(n)，但我不确定。

Answer 1

你的表达

sum_(i = 1)^n (1 / i)

是n-th harmonic number。

来自维基百科的文章：

n-th谐波数大约与n的自然对数一样大。原因是总和近似为积分：

int_1^n (1 / x) dx

其价值是ln(n)。

他们还给出了这个显示相关性的漂亮图像：

所以它是Theta(log n)。

有关证明的详细信息，请参阅Finding Big O of the Harmonic Series或Simple proof of showing the Harmonic number Hn=Θ(logn)，它非常简单。