主方法用于解决以下类型的重复
T（n）= a ++（n）且a≥1和b≥1为常数＆f（n）为函数且可解释为
通过递归在非负整数上定义T（n）。
T (n) = a T+ f (n)在分析递归算法的函数中, 常量和函数具有以下含义：
- n是问题的大小。
- a是递归中子问题的数量。
- n / b是每个子问题的大小。 （这里假定所有子问题的大小基本相同。）
- f（n）是递归调用之外完成的工作的总和, 其中包括问题的总和与子问题的解决方案的总和。
- 不可能总是根据需求绑定功能, 因此我们提出三种情况, 以告诉我们可以对功能应用哪种绑定。
主定理
在以下三种情况下, 有可能完成渐近紧定界：
情况1：如果f（n）=对于某个常数ε> 0, 则得出：
T (n) = Θ例：
T (n) = 8 T apply master theorem on it.解：
Compare T (n) = 8 T with
T (n) = a T
a = 8, b=2, f (n) = 1000 n2, logba = log28 = 3
Put all the values in: f (n) =
1000 n2 = O (n3-ε )
If we choose ε=1, we get: 1000 n2 = O (n3-1) = O (n2)由于该方程成立, 因此主定理的第一种情况适用于给定的递归关系, 因此得出以下结论：
T (n) = Θ
Therefore: T (n) = Θ (n3)情况2：如果为真, 则对于某个常数k≥0, 它：
F (n) = Θ then it follows that: T (n) = Θ例：
T (n) = 2 , solve the recurrence by using the master method.
As compare the given problem with T (n) = a T a = 2, b=2, k=0, f (n) = 10n, logba = log22 =1
Put all the values in f (n) =Θ , we will get
10n = Θ (n1) = Θ (n) which is true.
Therefore: T (n) = Θ
= Θ (n log n)情况3：如果对于某些常数ε> 0, f（n）=Ω成立, 并且对于某个常数c <1, 对于n的大值, 则f为真, 则：
T (n) = Θ((f (n))示例：解决递归关系：
T (n) = 2解：
Compare the given problem with T (n) = a T
a= 2, b =2, f (n) = n2, logba = log22 =1
Put all the values in f (n) = Ω ..... (Eq. 1)
If we insert all the value in (Eq.1), we will get
n2 = Ω(n1+ε) put ε =1, then the equality will hold.
n2 = Ω(n1+1) = Ω(n2)
Now we will also check the second condition:
2
If we will choose c =1/2, it is true:
∀ n ≥1
So it follows: T (n) = Θ ((f (n))
T (n) = Θ(n2)
