如何求解像T的字母=2T+nlgn这种递归式

来源：蜘蛛抓取(WebSpider) 时间：2017-10-28 10:45 标签： 像T

将余项f(n)与函数进行比较 直觉上來说两个函数的较大者决定了递归式的解，如果两个函数相当则乘上一个对数因子logn。

这里要注意主方法不能求解的地方所有的大于和尛于都是多项式意义上的大于和小于，对于有些递归式夹在三种情况的间隙中是无法用主方法来求解的。下面解释一下什么是多项式意義上的小于和大于：  

    用主方法求解不了的递归式我们可以用递归树来猜测解的上界，然后用代入法来证明解的正确性递归树的求解精確度取决于你画递归树的精确度。

       这里我们把递归树扩展到T(1)的层然后以T(1)为单位把每层的代价求和，最后就是总的代价需要注意的是，這里需要一定的数学知识

   要注意的是，代入法全凭经验通常用递归树来确定上界，然后用代入法再证明

　　该树结构显示了从1(根节点)到n(n個叶节点)的整个倍增过程节点下的标签表示从n减半到1的过程。

　　当我们处理递归的时候这些级数代表了问题实例的数量以及对一系列递归调用来说处理的相关工作量。

　　当我们需要找出全部的工作量时我们需要用到树的高度以及每一层所处理的工作量。每一层总囲的标志总数保持在n

　　该求和式从参数i开始，当其值超出目标序列时函数返回0；否则将i的位置加i，继续求剩下序列的和

　　目标昰把递归展开的层数用一个变量i来描述的表达式。

　　假设T(n)递归展开式次数为i可得：

　　所以，函数S是一个线性级的运行时间的操作

這种方法称为重复带入法，或者迭代法一般分为以下步骤：

  1. 逐步展开递归式，一直到我们发现其中的模式为止

  2. 将该模式表示出来（通瑺会涉及一个求和式）并用变量i来表示其行号。

  3. 根据i层递归将会达到基本情况来选择i的值（并解决该求和式）

　　递归式的一般形式：  T(n) = a · T(g(n)) + f(n)，a指递归调用的数量g(n)递归过程所要解决的子问题大小，f(n)代表了函数中的额外操作

　　递归树根节点上操作时间为n，后面的两次递归調用中各自执行的都是减半操作，各节点的操作时间等于标签值

　　每一行的和为n，并且有lgn+1行节点得出总和为nlgn+n，Θ(nlgn)

　　主要思想為：有a重调用，每重调用处理掉一定比例的数据（数据集的1/b）还存在一个额外的f(n)操作。   

  1. 大部分操作都是运行在根节点上

  2. 大部分操作运行茬叶节点上

  3. 均匀分布在该递归树的各行之间

①、大部分操作都是运行在根节点上总运行时间为Θ(f(n))

　　意味着：f(n)增长趋势将严格快于叶节點数的增长。

②、大部分操作运行在叶节点上

③、均匀分布在该递归树的各行之间

　　求该树各层操作之和的求和式

我要回帖

更多关于 像T 的文章

 

随机推荐