算法设计与分析 - 主定理Master theorem （分治法递推时间复杂度） - Java

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

英文原版不上了直接中文

定义

假设有递推关系式T(n)=aT(n/b)+f(n)

其中n为问题规模

a为递推的子问题数量

n/b为每个子问题的规模（假设每个子问题的规模基本一样）

f(n)为递推以外进行的计算工作，无需参加递归

定理

a≥1，b>1为常数，f(n)为函数，T(n)为非负整数。则有以下结果（分类讨论）：

（1）若f(n)=O(n^{log_b^a-ε)}存在ε>0，就是当n^{log_b^a}的阶高于f(n)时，可以存在ε使得n^{log_b^a-ε}和f(n)的阶相同。此时取T(n)=θ(n^{log_b^a)}

（2）若f(n)=Θ(n^{log_b^a)} 注意这时n^{log_b^a}的阶和f(n)的阶相同，不需要ε。此时取T(n)=Θ(n^{log_b^alogn)}

（3）若f(n)=Ω(n^{log_b^a+ε)}首先得存在ε>0，就是当n^{log_b^a}的阶低于f(n)时，可以存在ε使得n^{log_b^a+ε}和f(n)的阶相同,即有足够大的n，而当af(n/b)<=cf(n), c<1此时取T(n)=Θ(f(n))

定义二

递推式子可以为T(n)=aT(n/b)+cn^k 其中 cn^k 表示原问题分解成子问题和将子问题的解合并成原问题的解的时间，对其分析可得到

\[T(n) = \begin{cases}
O(n^{log_ba}) & a > b^k \\
O(n^k·log_bn) & a = b^k \\
O(n^k) & a < b^k
\end{cases}\]

示例

T(n) = 9T(n/3)+n

此时 a = 9, b = 3, k = 1, f(n) = n, 满足a > b^{k 所以套用定理条件1 T(n) = θ(n^{log_b^a}) = O(n²)}

T(n) = 2T(n/2)+2n

此时 a = 2, b = 2, k = 1, f(n) = 2n, 满足a = b^{k，所以套用定理条件2 T(n) = O(n^k·log_{b^{n) = O(nlog_2ⁿ⁾}}}

T(n) = 2T(n/4)+n²

此时 a = 2, b = 4, k = 2, f(n) = n², 满足 a < b^{k, 所以套用定理条件3 T(n) = O(n^k) = O(n²)}

T(n) = 2T(n½)+logn

a = 2, b = 1, f(n) = logn ... 不考暂且放置..

正文

算法设计与分析 - 主定理Master theorem （分治法递推时间复杂度）

定义

定理

定义二