算法的主方法算法的主方法|算法设计与分析

主方法用于解决以下类型的重复
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 Tapply master theorem on it.

解：

Compare T (n) = 8 Twith 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)