一算法概念与教学基础 for now <low to high if (sum 0) sum +=A[now] F (sum max now) i now <now max_now <sum if (sum <=e or now ==high) if (max now max) i max <-i now j_max <j_now max <max_now sum < else if(a[now】>) max_now <sum <-A[now] i_now <j_now <-i return (max,i_max,j_max) 51.4判断方法 替代法 包含两个步骤：猜测解的形式、归纳常数（直接替代）并证明解正确（要求易于猜得） 例：针对T(m)=2T(n/2)+n,先猜测解为Tm)=0(n1ogn),选取常数C>T2)+1即可 更复杂的例子：求T(m)=2T(n/2+17)+n的解的上界。 解法（平移的思路）：令n=m+34,可发现T(m+34)=2T(Lm/2+34)+m+34,由此T(m+34)+34= 2(T(m/2+34+34)+m类似上一种情况可直接估算出上界。 ◆猜测出渐近界未必能归纳成功，有时是因为归纳假设偏弱，可以尝试加强假设、调整低阶项、初等变换 等，如T()=2T(ln/2)+1,归纳假设cm无法继续，假设为m-2即可。 ◆不应将猜测无理由放大 *变量代换：对T(n)=2T(lV)+1ogm,取m=1ogn可发现最终结果为0(1ogn1og1ogm). **弊端：猜测、证明都可能困难 递归树 每个结点代表相应子问题代价，行和代表某层代价，总和得总代价 ◆一般用来获得猜测解再替代，省略大部分细节。也可细化直接解出结果。 例：T(m)=3T(ln/个)+Θ(n)→T(m)=3T(n/④+cm2简化，接着画出递归树求得复杂度大约为 ∑6cm2=cn2,因此为6(n2)量级 代价不相同：T(m)=T/3)+T(2n/3)+O(,作出递归树可发现每层的和为cm,再由行数（通过解方 程可计算出层数具体值，不过估算中没有精确必要)为O(1og)可知复杂度O(n1ogm)。同理，对于 T(m)=T(n/纠+T(/2)+n2,可类似算得结果为等比级数的n2倍，仍为n2量级。 *关健为求行和与总代价，需要上下行和的关联 主方法一 算法概念与数学基础 7 for now <‐ low to high if (sum > 0) sum += A[now] if (sum > max_now) j_now <‐ now max_now <‐ sum if (sum <= 0 or now == high) if (max_now > max) i_max <‐ i_now j_max <‐ j_now max <‐ max_now sum <‐ 0 else if (A[now] > 0) max_now <‐ sum <‐ A[now] i_now <‐ j_now <‐ i return (max,i_max,j_max) §1.4 判断方法 替代法 包含两个步骤：猜测解的形式、归纳常数 (直接替代) 并证明解正确 (要求易于猜得) 例：针对 T(n) = 2T(⌊n/2⌋) + n，先猜测解为 T(n) = O(n log n)，选取常数 C > T(2) + 1 即可。 更复杂的例子：求 T(n) = 2T(⌊n/2⌋ + 17) + n 的解的上界。 解法 (平移的思路)：令 n = m+34，可发现 T(m+34) = 2T(⌊m/2⌋+34)+m+34，由此 T(m+34)+34 = 2(T(⌊m/2⌋ + 34) + 34) + m 类似上一种情况可直接估算出上界。 *猜测出渐近界未必能归纳成功，有时是因为归纳假设偏弱，可以尝试加强假设、调整低阶项、初等变换 等，如 T(n) = 2T(⌊n/2⌋) + 1，归纳假设 cn 无法继续，假设为 cn − 2 即可。 *不应将猜测无理由放大 *变量代换：对 T(n) = 2T(⌊ √ n⌋) + log n，取 m = log n 可发现最终结果为 O(log n log log n)。 **弊端：猜测、证明都可能困难 递归树 每个结点代表相应子问题代价，行和代表某层代价，总和得总代价 *一般用来获得猜测解再替代，省略大部分细节。也可细化直接解出结果。 例：T(n) = 3T(⌊n/4⌋) + Θ(n 2 ) =⇒ T(n) = 3T(n/4) + cn2 简化，接着画出递归树求得复杂度大约为 ∑∞ i=0 3 i 16i cn2 = c ′n 2，因此为 Θ(n 2 ) 量级。 代价不相同：T(n) = T(n/3) + T(2n/3) + O(n)，作出递归树可发现每层的和为 cn，再由行数 (通过解方 程可计算出层数具体值，不过估算中没有精确必要) 为 O(log n) 可知复杂度 O(n log n)。同理，对于 T(n) = T(n/4) + T(n/2) + n 2，可类似算得结果为等比级数的 n 2 倍，仍为 n 2 量级。 *关键为求行和与总代价，需要上下行和的关联 主方法