设计与分析 - 马斯特定理

马斯特定理是用于计算算法时间复杂度的众多方法之一。在分析中，通过计算时间复杂度来找出算法的最佳逻辑。马斯特定理应用于递推关系。

但在我们深入研究主定理之前，让我们首先回顾一下什么是递推关系 -

递归关系是定义元素序列的方程，其中一项是其前一项的函数。在算法分析中，递归关系通常是在算法中存在循环时形成的。

问题陈述

马斯特定理只能应用于递减和除法循环函数。如果关系不是递减或除除，则不能应用马斯特定理。

函数除法的马斯特定理

考虑类型的关系 -

T(n) = aT(n/b) + f(n)

其中，a >= 1且b > 1，

n - 问题的大小

a - 递归中的子问题数

n/b - 基于所有子问题大小相同的假设的子问题的大小。

f(n) - 表示递归之外完成的工作成本 -> θ(nk logn p) ，其中 k >= 0 并且 p 是实数；

如果递推关系是上面给定的形式，那么主定理中存在三种情况来确定渐近符号 -

如果 a > b ^k，则 T(n)= θ (n ^{logb a} ) [ log _b a = log a / log b。]
如果 a = b ^k
- 如果 p > -1，则 T(n) = θ (n ^{logb a} log ^p+1 n)
- 如果 p = -1，则 T(n) = θ (n ^{logb a} log log n)
- 如果 p < -1，则 T(n) = θ (n ^{logb a} )
如果 a < b ^k，
- 如果 p >= 0，则 T(n) = θ (n ^k log ^p n)。
- 如果 p < 0，则 T(n) = θ (n ^k )

马斯特递减函数定理

考虑类型的关系 -

T(n) = aT(n-b) + f(n)
where, a >= 1 and b > 1, f(n) is asymptotically positive

这里，

n - 问题的大小

a - 递归中的子问题数

nb - 基于所有子问题大小相同的假设的子问题的大小。

f(n) - 表示在递归之外完成的工作成本 -> θ(n ^k )，其中 k >= 0。

如果递推关系是上面给定的形式，那么主定理中存在三种情况来确定渐近符号 -

如果 a = 1，则 T(n) = O (n ^k+1 )
如果 a > 1，则 T(n) = O (a ^n/b * n ^k )
如果 a < 1，则 T(n) = O (n ^k )

例子

应用主定理除以递推关系的几个例子-

实施例1

考虑递推关系，如 T(n) = 8T(n/2) + n ²

In this problem, a = 8, b = 2 and f(n) = Θ(n^k log_n p) = n², giving us k = 2 and p = 0.
a = 8 > b^k = 22 = 4,
Hence, case 1 must be applied for this equation.
To calculate, T(n) = Θ (n^{logb a} )
   = n^log₂⁸
   = n^{( log 8 / log 2 )}
   = n³
Therefore, T(n) = Θ(n³) is the tight bound for this equation.

实施例2

考虑递推关系，如 T(n) = 4T(n/2) + n ²

In this problem, a = 4, b = 2 and f(n) = Θ(n^k log_n p) = n², giving us k = 2 and p = 0.
a = 4 = b^k = 2² = 4, p > -1
Hence, case 2(i) must be applied for this equation.
To calculate, T(n) = Θ (n^{logb a} log^p+1 n)
   = n^log₂⁴ log⁰⁺¹n
   = n²logn
Therefore, T(n) = Θ(n²logn) is the tight bound for this equation.

实施例3

考虑递推关系，如 T(n) = 2T(n/2) + n/log n

In this problem, a = 2, b = 2 and f(n) = Θ(n^k log_n p) = n/log n, giving us k = 1 and p = -1.
a = 2 = b^k = 2¹ = 2, p = -1
Hence, case 2(ii) must be applied for this equation.
To calculate, T(n) = Θ (n ^{logb a} log log n)
   = n^log₄⁴ log logn
   = n.log(logn)
Therefore, T(n) = Θ(n.log(logn)) is the tight bound for this equation.

实施例4

考虑递推关系，如 T(n) = 16T(n/4) + n ² /log ² n

In this problem, a = 16, b = 4 and f(n) = Θ(n^k log_n p) = n²/log²n, giving us k = 2 and p = -2.
a = 16 = b^k = 4² = 16, p < -1
Hence, case 2(iii) must be applied for this equation.
To calculate, T(n) = Θ (n ^{logb a})
   = n^log₄¹⁶
   = n²
Therefore, T(n) = Θ(n²) is the tight bound for this equation.

实施例5

考虑递推关系，如 T(n) = 2T(n/2) + n ²

In this problem, a = 2, b = 2 and f(n) = Θ(n^k log_n p) = n², giving us k = 2 and p = 0.
a = 2 < b^k = 2² = 4, p = 0
Hence, case 3(i) must be applied for this equation.
To calculate, T(n) = Θ (n^k log^p n)
   = n² log⁰n
   = n²
Therefore, T(n) = Θ(n²) is the tight bound for this equation.

实施例6

考虑递推关系，如 T(n) = 2T(n/2) + n ³ /log n

In this problem, a = 2, b = 2 and f(n) = Θ(n^k log_n p) = n³/log n, giving us k = 3 and p = -1.
a = 2 < b^k = 2³ = 8, p < 0
Hence, case 3(ii) must be applied for this equation.
To calculate, T(n) = Θ (n^k)
   = n³
   = n³
Therefore, T(n) = Θ(n³) is the tight bound for this equation.

在减少递推关系中应用大师定理的几个例子-

实施例1

考虑递推关系，如 T(n) = T(n-1) + n ²

In this problem, a = 1, b = 1 and f(n) = O(n^k) = n², giving us k = 2.
Since a = 1, case 1 must be applied for this equation.
To calculate, T(n) = O(n^k+1)
   = n²⁺¹
   = n³
Therefore, T(n) = O(n³) is the tight bound for this equation.

实施例2

考虑递推关系，如 T(n) = 2T(n-1) + n

In this problem, a = 2, b = 1 and f(n) = O(n^k) = n, giving us k = 1.
Since a > 1, case 2 must be applied for this equation.
To calculate, T(n) = O(a^n/b * n^k)
   = O(2^n/1 * n¹)
   = O(n2ⁿ)
Therefore, T(n) = O(n2ⁿ) is the tight bound for this equation.

实施例3

考虑递推关系，如 T(n) = n ⁴

In this problem, a = 0 and f(n) = O(n^k) = n⁴, giving us k = 4
Since a < 1, case 3 must be applied for this equation.
To calculate, T(n) = O(n^k)
   = O(n⁴)
   = O(n⁴)
Therefore, T(n) = O(n⁴) is the tight bound for this equation.