主定理的推导 Master theorem

作者: 荷茗 | 来源:发表于2018-12-08 12:54 被阅读14次

主定理的推导 Master theorem
算法基础-01.算法复杂度的计算-主定理
master theorem 推导
快速排序及主定理
算法复杂度基础-主定理
有心力问题（4）: 维里定理
（4.2）James Stewart Calculus 5th
CAP定理（CAP theorem）
小马哥课堂-统计学-中心极限定理
请简述 CAP 原理

关于递推问题算法复杂度的的推导。
递推公式： $T(n) = aT(\frac{n}{b})+O(n^{d}), a>0,b>1,d\geq 0$

分三种情况:
$T(n) = \begin{cases} O(n^{d}) & \text{if } d > log_{b}a \\ O(n^{d} logn) & \text{if }d = log_{b}a \\ O(n^{log_{b}a})&\text{if } d < log_{b}a \end{cases}$

由递推公式可得:
$T(n) \leq cn^{d} \sum_{i=0}^{log_{b}n-1}(\frac{a}{b^d})^i$

$\text{let } r= \frac{a}{b^d}$

$\text{If } r > 1,\ T(n) \leq cn^{d} \frac{r^{log_bn} - 1} {r- 1}$

$r^{log_bn} = r^\frac{log_rn}{log_rb} = n ^{\frac{1}{log_rb}} = n ^{\frac{1}{\frac{log_bb}{log_br}}} = n ^{ log_br}$

$cn^{d} \frac{r^{log_bn} - 1} {r- 1} = c \frac{n^{d} (n ^{ log_br} -1)} {r- 1} \leq c \frac{n^{d} n ^{ log_br}} {r- 1} = c \frac{n^{d} n ^{ log_ba-log_bb^d}} {r- 1} = \frac{c n^{log_ba}}{r-1} = O(n^{log_ba})$

$\text{If } r < 1, T(n) = cn^{d} \sum_{i=0}^{log_{b}n-1}(r)^i \leq cn^{d}\sum_{i=0}^{\infty}(r)^i = cn^{d}\cdot \frac{1}{1-r} = O(n^d)$

主定理的推导 Master theorem
关于递推问题算法复杂度的的推导。递推公式：分三种情况: 由递推公式可得:
算法基础-01.算法复杂度的计算-主定理
主定理的定义『在算法分析中，主定理（英语：master theorem）提供了用渐近符号（大O符号）表示许多由分...
master theorem 推导
Let a and b > 1 be constants, let f(n) be a function, and...
快速排序及主定理
主定理，主定理（英语：master theorem）提供了用渐近符号表示许多由分治法得到的递推关系式的方法在分治...
算法复杂度基础-主定理
在算法分析中，主定理（英语：master theorem）提供了用渐近符号（大O符号）表示许多由分治法得到的递推关...
有心力问题（4）: 维里定理
有心力运动的另一特性还可由一个更为一般的定理推导。维里定理(virial theorem)适用于各种不同的系统，...
（4.2）James Stewart Calculus 5th
The Mean Value Theorem 中值定理先了解 Rolle’s Theorem 罗尔定理 Roll...
CAP定理（CAP theorem）
CAP定理（CAP theorem）在计算机科学中, CAP定理（CAP theorem）, 又被称作布鲁尔定理...
小马哥课堂-统计学-中心极限定理
Central limit theorem(中心极限定理) the central limit theorem (...
请简述 CAP 原理
什么是CAP？ CAP 定理（CAP theorem）又被称作布鲁尔定理（Brewer's theorem），是加...