※ 引述《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://www.ptt.cc/bbs/Math/M.1713287114.A.19C.html