学习主定理

Posted on Edited on

之前很早就听机房的学长说主定理了，是用于算法竞赛中分析时间复杂度的，但是一直没有学习过

今天做DS，又遇到了，题目如下

一道考研题目

解析：时间复杂度为

设 ，有

由此得到递推公式

故

带回 得到 即时间复杂度为

这也就是归并排序(MergeSort)的时间复杂度

更普适的

假设有递推关系式 ，其中

其中， 为问题规模， 为递归的子问题数量， 为每个子问题的规模（假设每个子问题的规模基本一样）， 为递归以外进行的计算工作

结论：

  1. 若存在，（可不严谨的视作多项式地小于），那么
  2. 若存在，，那么
  3. 若存在，（多项式地大于），同时存在常数 以及充分大的，满足，则

符号说明：

更普适的:

算法证明

更本质的:

使用 为例

1
2
3
4
5
6
7
8
                    f(n)
                /            \
        f(n/b)                f(n/b)
        /        \                /        \
f(n/b^2) f(n/b^2) f(n/b^2) f(n/b^2)
    /    \        /    \        /    \        /    \
    ......(很多次递归以后)
    O(1)O(1)......O(1)O(1)O(1)O(1)

这里用准确的说是

主定理到底在做什么？事实上主定理就是对比这两个部分的时间复杂度罢了

到底是上面那些f(n)操作加起来更耗时, 还是最下层所有叶节点的O(1)加起来更耗时?

即对于 ， 我们认为它是常数，重点是 ，大致数值为

代换一下，得到 ，显然这是在对比两项

对于三种情况：

  1. 下层所有叶节点的O(1)加起来更耗时

    （即 ）的增长速度大于了 , 那么

    之所以引入 只是为了说明增长速度大

    第一种情况下 代表的最终处理问题的最小子任务明显占了主导

  2. 一样耗时

    最小子任务和分割过程一样，没有谁明显的占据了主导低位，因此两个的时间复杂度都得算进去

  3. 上面那些f(n)操作加起来更耗时

    分治过程占了主导地位，同时这种情况下限制了 不会无法被认为是常数

常见形式

例题

  1. NOIP2016TGT14

根据主定理，此时

符合格式 (2)，此时

所以

选择C

根据主定理，此时 符合格式 (1)，此时

所以

根据主定理，此时 符合格式 (2)，此时

所以

根据主定理，此时 符合格式 (3)，此时

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

所以

小结

主定理讨论的是对于公式 里 p f(n) k 三个变量的增长速度。只不过主定理直接用条件限制了p，所以我们关注的重点就仅在 f(n) 和 k 上了

reference

https://zh.wikipedia.org/wiki/%E4%B8%BB%E5%AE%9A%E7%90%86

https://blog.restkhz.com/post/how-master-theorem-works

https://blog.csdn.net/lanchunhui/article/details/52451362

https://www.luogu.com.cn/article/w3avh1ku

https://www.mashangxue123.com/tutorials/dsa/master-theorem/

https://www.cnblogs.com/coderzjz/p/14272460.html