解：依题：
适用主方法的第二种情况有：
解：依题：
求解这个这个递归式可以不用递归树和主方法
我们可以看到递归每次规模减半，且每次的时间代价都是数组规模大小 N
故
解：允许一些不精确，递归式改写为
则：
而 
尝试使用主方法的第三种情况：
，
考虑正则条件：
$，代入即
即可满足正则条件
故
解：允许一些不精确，将递归式改写为
则：
故采用主方法的第二种情况有：
解：允许一些不精确，将递归式改写为
递归树如下：
故采用主方法的第二种情况，
解：允许一些不精确，将递归式改写为
则：
故采用主方法的第二种情况有：
若有收获，就点个赞吧
0 人点赞
