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

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