主定理（Master Theorem）推导和理解（2） - 码农知识堂

主定理（Master Theorem）推导和理解（2）

主定理的证明，见主定理（Master Theorem）推导和理解（1）_Happy_Traveller的博客-CSDN博客，看几个实际case。

Case 1：求解递推方程：

，T(n)的计算复杂度

依据主定理，a=1, b=3, f(n) = n，那么

$n^{log_{3}^{9}} = n^{2}, Obviously, f(n) = O(n^{log_{3}^{9} - 1}) (\varepsilon = 1) \\ |\quad So,T(n) = O(n^{2})$

Case 2 : 求解递推方程：

, T(n)的计算复杂度

依据主定理，a=1, b=2/3, f(n) = 1，那么

$a = 1, b=3/2, f(n) = 1, Obviously, f(n) = \Theta (n^{log_{3/2}^{1}}) = \Theta (n^{0}) = \Theta (1) \\ | \quad So, T(n) = \Theta (logn)$

Case 3 : 求解递推方程：

, T(n)的计算复杂度

依据主定理，a=3, b=4, ，那么

$nlogn = \Omega (n^{log_{4}^{3} + \varepsilon}) = \Omega (n^{0.793 + \varepsilon}), So, 0 < \varepsilon < 0.207 \\ |\quad Meanwile, af(n/b)\leq cf(n), \frac{3n}{4}log\frac{n}{4} \leq cnlogn, So, c \geq \frac{3}{4} \\ |\quad So, T(n) = \Theta (f(n)) = \Theta (nlogn)$

Case 4 : 求解递推方程：

，T(n)的计算复杂度

依据主定理，a=2, b=2, f(n) = nlogn，那么

$log_{b}^{a} = n^{log_{2}^{2}} = n, f(n)=nlogn, can't \enspace find \enspace \varepsilon, make\enspace nlogn = \Omega (n^{1+\varepsilon})$

所以case 4不能使用主定理

同时，直观上看，递推方程中，将原问题拆成b个子问题，同时需要a个这样的子问题，同时需要f(n)的操作合并这些子问题，所以，如果b越大，a越小，同时f(n)步骤越少，总体的计算就越少，就是越是好的算法。
相关阅读:
API 接口：原理、设计与应用
 国内最牛的Java面试八股文合集，不接受反驳我这该死的魅力
 国产AI绘画软件“数画”刷爆朋友圈，网友到底在画什么
 前端新手Vue3+Vite+Ts+Pinia+Sass项目指北系列文章 —— 第十一章基础界面开发 (组件封装和使用)
JTS: 17 DiscreteHausdorffDistance 豪斯多夫距离计算
 Git分布式版本控制工具
 Bun 1.0.7 版本发布，实现多个 Node.js 兼容改进
 EdrawMax思维导图,EdrawMax组织结构图
 【Java SE】类和对象
 6.Tomcat概述与部署
原文地址：https://blog.csdn.net/zhangsj1007/article/details/127719436