申論題 - 阿摩線上測驗

申論題資訊

試卷：104年 - 104年地方四等-程式設計概要#35322
科目：程式設計
年份：104年
排序：0

六、假設有一個演算法，它的計算量可寫成如下的遞迴式 T(n)= T(n-1)+ 1/ n，T(1)=1，請問此演算法的時間複雜度為何？（8 分）

詳解提供者：hchungw

T(n)實際上是前n個自然數倒數的和。這種和被稱為調和級數，其增長速率接近於自然對數 ln(n)。因此，我們可以說 T(n) 的時間複雜度接近於 O(lnn)。