主定理

摘要

花个 10 分钟学一学主定理

形式

假设有递归关系式

其中 . 为问题规模,而 a 为递归子问题的数量, 为字问题规模(假设每个子问题的规模基本一样), 为递回以外进行的计算工作(可以理解为合并代价)

情形 1

如果存在常数 使得

那么

情形 2

如果存在常数 ,有

情形 3

如果存在常数 使得

同时存在常数 以及充分大的 n 满足


  转载请注明: Sshwy's Blog 主定理

 上一篇
浅谈一类分治算法 浅谈一类分治算法
摘要 仍然是啃论文,这次啃一啃数据结构的部分 修改与询问我们常常遇到数据结构题,要求我们维护修改与询问的操作。这些题目的要求各不相同,而操作之间的关系也各不相同。在满足特定关系的操作中,我们利用条件的线性性与相关性,可以将一类动态问题转化
2019.05.05
下一篇 
网络流入门之费用流 网络流入门之费用流
摘要 之前写的《网络流初步》内容太多,因此单独分一个费用流出来。本文的内容可能涉及到《网络流入门之最大流》的内容,建议先食用后者。 2019.6.15 编入精选文章 费用流给定一个网络 ,每条边除了有容量限制 $c(u,
2019.05.03
  目录