时间复杂度对数阶是什么样的T(n)=T(n-1)+1/n=T(n-2)+1/(n-1)+1/n=T(n-3)+1/(n-2)+1/(n-1)+1/n……=T(2)+1+1/2+…+1/(n-1)+1/n=1+1+1/2+…+1/(n-1)+1/n=得O(logn)为什么是对数阶?

Question

时间复杂度对数阶是什么样的
T(n) = T(n-1)+1/n
= T(n-2)+1/(n-1)+ 1/n
= T(n-3)+1/(n-2) +1/(n-1)+ 1/n
……
= T(2)+1+1/2+… +1/(n-1)+ 1/n
= 1+1+1/2+… +1/(n-1)+ 1/n
=得O(logn)
为什么是对数阶?

Answer 1

当n趋于无穷大时调和级数有：(1 + 1/2 + 1/ 3 + 1/ 4.) - lnn ~ c
因此该时间复杂度为O(logn)