民國109年 第2梯次 電腦軟體設計(JAVA)乙級 學科
第6題
若n>=1 時,T(n)=T(n-1)+1/n,且 ,T(n)之複雜度何者正確?
題目
若n>=1 時,T(n)=T(n-1)+1/n,且 ,T(n)之複雜度何者正確?
- (1) θ(n log n)
- (2) θ(n 2)
- (3) θ(n)
- (4) θ(log n)
官方答案
(4) θ(log n)
解析
將遞迴式展開，T(n)=T(n-1)+1/n，反覆代入可得 T(n)=T(1)+Σ(1/k)（k=2..n），即調和級數 H_n 減常數。已知調和級數 H_n = 1+1/2+...+1/n ≈ ln n + γ（歐拉常數），故 T(n)=Θ(log n)。其他選項：Θ(n)、Θ(n log n)、Θ(n²) 成長皆過快；本題只累加 1/k，總和受對數界定。故選 4。
AI 參考解析（推得答案已與官方答案比對一致），非官方公告內容，僅供備考參考。