算法的主方法

主方法用于解决以下类型的重复

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)