Question

算法导论里面的大师解法是什么 用大师解法计算下面递归表达式的时间复杂度. T(n)=2T(n/2) + Θ(n^0.1)？

Answer 1

#a i从0循环到n，算法复杂度为O(n)。
#b 一共要做n^2/2次加法，算法复杂度为O(n^2)。
#c 要求一个k，满足2^k>=n ，算法复杂度为O(log(n))
#d 注意到这个函数做的事跟#c的函数恰好相反，算法复杂度相同，也是O(log(n))
#e 因为已算出#g每次做3(n-3)次加法，那么i从1到n，一共做2/3*(n^2-5n+6)次加法，所以复杂度为O(n^2)。
#f 这个函数可以写成公式T(n)=T(n-2)+T(n-1)，这个递归式跟黄金分割有关系，解这个递归式，可以知道 T(n) = O((√5-1/2)^n)
#g 函数调用一共做3(n-3)次加法，所以复杂度为O(n)
PenitentSin 这位兄台的#c 算的不对啦，#g也不对。还有#f，这个虽然是递归，但不是递归就等于指数级的复杂度，要解递归方程才能断定的。
关于算法复杂度，《算法导论》一书中第四章有一个主定理，记住这个定理之后，这些问题就小case了（除了复杂递归之外）。