用途

实用主义为上，我们先讲用途。
我们使用master theorem的通常目的是，用递归关系解决了分治问题后，快速地由这个已知的递归关系求出其时间复杂度。

前置知识/准备

如果你是为了打OI（或是为了应试的本科生），那么你甚至不需要了解递归树(recursive tree)或数列求和。 只需要了解怎么用就行了，可以跳过这一节。
如果你想要深入了解或是证明，那么我推荐你尝试求解一些确定的递推式的时间复杂度，每次求解都画个recursive tree慢慢分析。当你得出结果，并察觉到这些不同的递推式之间的求解过程有相同之处时。恭喜你，你已经成功掌握了master theorem的核心所在，尽管你可能还没有完全推导出一个严谨的数学证明。
当然如果你写了几道题就直接证出来这个定理了的话，请容许我跪见大佬以示尊重（手动删除）。 下面是我推荐求解的一些确定的递推式：

1. $T(n)=4T(n/2)+O(n)$
2. $T(n)=3T(n/2)+O(n)$
3. $T(n)=2T(n/2)+O(n)$
4. $T(n)=2T(n/2)+O(n^2)$

下面其时间复杂度：

1. $T(n)=O(n^2)$
2. $T(n)=O(n^{\log_2 3})$
3. $T(n)=O(n\log_2 n)$
4. $T(n)=O(n^2)$

简便使用方法

对于以下形式的递推式 $T(n) = aT(\lceil \frac{n}{b} \rceil) + f(n^d),(a > 0, b > 1, d \geq 0)$
求解其时间复杂度，直接带入对应参数即可。

证明

暂且挖坑，文字表述毕竟不如图像呈现的更直观，观看视频更好

测验

如果你已经完全掌握了，那么来小试牛刀下吧。
求出下列递推式的时间复杂度的确界

1. $T(n)=4T(n/5)+\log n$
2. $T(n)=T(\sqrt{n})+5$

参考

快速了解
递归树(recursive tree)
补充
简单补充