算法分析---主定理
在算法分析中，主定理（英语：master theorem）提供了用渐近符号表示许多由分治法得到的递推关系式的方法。此方法经由经典算法教科书《算法导论》而为人熟知。不过，并非所有递推关系式都可应用主定理。该定理的推广形式包括Akra-Bazzi定理。
假设有递推关系式
，其中
为问题规模，为
递推的子问题数量，
为每个子问题的规模（假设每个子问题的规模基本一样），
为递推以外进行的计算工作。
情形一：
1、LINUX 压缩目录成一个压缩文件
2、MFC中的句柄
3、大佬参考文章
4、Layui文件上传和表单提交
5、解决Linux关闭终端（关闭SSH等）后运行的程序或者服务自动停止【后台运行程序】
如果存在常数，有
，并且是多项式的小于
那么
情形二：
如果存在常数k≥0，有
那么
情形三：
如果存在常数，有
- ，并且是多项式的大于
同时存在常数以及充分大的，满足
那么
常用算法中的应用：
| 算法 | 递推关系式 | 运算时间 | 备注 |
|---|---|---|---|
| 折半搜索 | 情形二（k=0） | ||
| 二叉树遍历 | 情形一 | ||
| 归并排序 | 情形二（k=0） |
1、LINUX 压缩目录成一个压缩文件
2、MFC中的句柄
3、大佬参考文章
4、Layui文件上传和表单提交
5、解决Linux关闭终端（关闭SSH等）后运行的程序或者服务自动停止【后台运行程序】