我猜以下展开式会给你适当的提示:T(n) == 1/lg(n) + T(n-1)= 1/lg(n) + 1/lg(n-1) + T(n-2)= 1/lg(n) + 1/lg(n-1) + 1/lg(n-2) + T(n-3)= ···= 1/lg(n) + ··· + 1/lg(n/2) + T(n/2)= Theta(n/lg(n)) + T(n/2)现在,对这个新的递归式使用主定理。