【精选】3求解递归.pdf

本讲内容 • 求解递归 – 代换法（Substitution method ） – 递归树法（Recursion-tree method ） – 主方法（master method ） • 递归求解的例题 2 代换法 • 代换法求解递归式的三个步骤 – 猜测解的形式 – 用数学归纳法证明 • 找出使解有效的常数 – 确定常数使边界条件成立 4 例：T(n) = 4T(n/2) + n • [假定T(1)=Θ(1)] 3 • 猜测T(n)= Ο (n ) （分别证明Ο和Ω 关系） • 假设，对于所有的kn T(k) ≤ ck3 • 通过归纳法证明 T(n) ≤ cn3 5 例：T(n) = 4T(n/2) + n T(n) = 4T(n/2) + n ≤ 4c(n/2)3 + n = (c/2)n3 + n = cn3 – ((c/2)n3 – n) 期望的形式 - 余项 ≤ cn3 期望的形式 这里要保证：((c/2)n3 – n) ≥ 0， 这只需要：c ≥ 2并且n ≥ 1 余项 11 例：T(n) = 4T(n/2) + n • 还必须处理初始情形，才能使归纳成立。 • 因为对所有的1≤nn0 都有T(n)=Θ(1) ，其中 n 是某个适当的常数 0 • 于是当1≤nn 时，只要c足够大，就有 0 “Θ(1)” ≤ cn3 • 但这个界并不够紧 12 更紧的上界 2 • 我们来证明T(n) = Ο (n ) • 假设对于所有的kn ，有T(k) ≤ ck2 T(n) = 4T(n/2) + n ≤ 4c(n/2)2 + n 2 = Ο (n ) 13 更紧的上界 2 • 我们来证明T(n) = Ο (n ) • 假设对于所有的kn ，有T(k) ≤ ck2 T(n) = 4T(n/2) + n ≤ 4c(n/2)2 + n 2 = Ο (n ) 错！必须证明完全一致的形式 = cn2 – (-n) 期望的形式 - 余项 ≤ cn2 但对任何c 0 ，上式最后一步不可能成