作者cuteSquirrel (可爱的小松鼠)
看板Math
标题Re: [中学] Σ问题
时间Wed Apr 17 01:05:12 2024
※ 引述《suspect1 ()》之铭言:
: 请教大大
: n
: 为何 Σ 1/i = O( log n ) ??
: i=1
n
Σ 1/i = 1/1 + 1/2 + ... + 1/n
i=1
= 1 * (1/1) + 1 * (1/2) + ... + 1 * (1/n)
= 高度为1宽度为1的长方形+高度为1/2宽度为1的长方形+...+高度为1/n宽度为1的长方形
n
~近似 ∫ 1/x dx 相当於 y = 1/x 的曲线下面积,从x=1积分到x=n
x=1
x=n
= [ ln(x) ]
x=1
= ln(n) - ln(1)
= ln(n) - 0
= ln(n)
= O( ln(n) ) 上边界order 为 ln(n) = log n
e
= O( log(n) ) 由换底公式可得 log n = log n / log 10, 常数项不影响order
10 e e
这边的 O 采用 计算理论 或者 演算法 最常见的定义,复杂度的上边界。
要更严谨的数学推导可参考微积分课本关於Harmonic series 的证明。
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 114.37.172.44 (台湾)
※ 文章网址: https://webptt.com/cn.aspx?n=bbs/Math/M.1713287114.A.19C.html