和 1 / i 的渐近符号
Asymptotic notation of sum 1 / i
的渐近符号是什么
即
sum_(i = 1)^n (1 / i)
首先，这不是作业。第二，由于没有计算分数的公式，我不知道如何用n表达这个求和并得到渐近符号.
可能是Theta(n)，但我不确定。
你的表情
sum_(i = 1)^n (1 / i)
就是n-th harmonic number.
来自维基百科文章：
The n-th harmonic number is about as large as the natural logarithm of n. The reason is that the sum is approximated by the integral:
int_1^n (1 / x) dx
whose value is ln(n).
他们还给出了这张显示相关性的漂亮图片：
原来是Theta(log n).
证明详见Finding Big O of the Harmonic Series or Simple proof of showing the Harmonic number Hn=Θ(logn)，很简单
即
sum_(i = 1)^n (1 / i)
首先，这不是作业。第二，由于没有计算分数的公式，我不知道如何用n表达这个求和并得到渐近符号.
可能是Theta(n)，但我不确定。
你的表情
sum_(i = 1)^n (1 / i)
就是n-th harmonic number.
来自维基百科文章：
The
n-thharmonic number is about as large as the natural logarithm ofn. The reason is that the sum is approximated by the integral:
int_1^n (1 / x) dxwhose value is
ln(n).
他们还给出了这张显示相关性的漂亮图片：
原来是Theta(log n).
证明详见Finding Big O of the Harmonic Series or Simple proof of showing the Harmonic number Hn=Θ(logn)，很简单