2017-03-19 13:27:15 +0000   |     algorithm master theorem   |   Viewed times   |    

主定理(Master Theorem)

主定理的本质,就是看一个递归函数的复杂度是由前半部分子问题规模主导,还是后半部分每一层的递归代价主导。

对于一个递归式,

前半部分 描述了递归子问题的规模。后半部分 代表了每一层递归的代价。随着递归的深入,函数的总体复杂度是整个递归树每一层复杂度的总和。根据复杂度计算的渐进原则,一些次要的复杂度会被修剪掉。

master-theorem

master-theorem

具体分为以下三种情况,

  1. 适用于主定理 case 1

    前半部分 ,多项式意义地大于后半部分 。所以 的复杂度由前半部分主导。

  2. 适用于主定理 case 2

    前半部分 , 和后半部分1同阶。所以 的复杂度等于每层的规模1 乘以递归深度 ,等于

  3. 适用于主定理 case 3

    后半部分 多项式意义地大于前半部分 。所以 的复杂度由后半部分 主导。

例外情况

但有些情况会掉进case 2case 3的缝隙里,

适用于主定理 case 2 的一个推广:

前半部分 与后半部分 同阶。所以 的复杂度等于每层的规模 乘以递归深度 ,等于

至于为什么 不是多项式地大于 ,是因为多项式意义上的大于是指像下面这种情况,

所以,我们可以说 是多项式意义上大于

但换成 就不行,对数 在数量级上比 低了一阶,所以 渐进小于