算法|算法分析（复发）|问题1

重复发生的价值是什么。

T(n) = T(n/4) + T(n/2) + cn2
T(1) = c
T(0) = 0

c常数为正

（A） O（n） ^3. ) （B） O（n） ^2. ) （C） O（n） ^2. Logn） （D） O（nLogn） 答复: （B） 说明： 下面是给定递归关系的初始递归树。

           cn^2
         /      
     T(n/4)     T(n/2)

如果我们进一步分解n/T，得到下面的表达式。

               cn^2
           /                 
       c (n^2)/16       c(n^2)/4
      /                /     
  T(n/16)     T(n/8)  T(n/8)    T(n/4) 

进一步分解会让我们产生以下结果

                 cn^2
            /                   
       c(n^2)/16           c(n^2)/4
       /                  /      
c(n^2)/256  c(n^2)/64  c(n^2)/64    c(n^2)/16
 /          /        /             /        
 

要知道T（n）的值，我们需要逐级计算树节点的和。如果我们对上面的树逐级求和，我们得到下面的序列 T（n）=c（n^2+5（n^2）/16+25（n^2）/256）+…。 上述系列为几何级数，比例为5/16 为了得到一个上界，我们可以将上述级数求和为无限项。我们得到的和是（n^2）/（1-5/16），也就是O（n^2）

有关更多详细信息，请参阅下面的视频讲座。 http://www.youtube.com/watch?v=whjt_N9uYFI 这个问题的小测验