时间复杂度对数阶是什么样的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)为什么是对数阶? 数学
网友回答
【答案】 当n趋于无穷大时调和级数有：(1 + 1/2 + 1/ 3 + 1/ 4.) - lnn ~ c
因此该时间复杂度为O(logn) 追问： 还是不太明白。。 追答： 就是说1 + 1/2 + 1/3 +... 和lnn同阶，就时间复杂度而言，所有的对数只是相差一个系数而已被忽略掉了