算法设计和分析减治法.ppt

第5章减治法 城治法的基本剧想 将规模为n的问题递减为规模为n-1或n/2的 子问题,反复递减后对子问题分别求解,再建立 子问题的解与原问题的解的关系 减常数(如1:每此迭代规模减小nn-1 规模为n 的问题 规模为n-1 的子问题 f(n)=f(n-1'an>1 子问题的解 原始问题的解 减因子(如1/2:每此迭代规模减半nn/2 规模为n 的问题 规模为n/2 a=(an2)2n是偶数 的子