更新时间:2021-04-27 18:58
分治,字面上的解释是“分而治之”,就是把一个复杂的问题分成两个或更多的相同或相似的子问题,再把子问题分成更小的子问题……直到最后子问题可以简单的直接求解,原问题的解即子问题的解的合并。在计算机科学中,分治法就是运用分治思想的一种很重要的算法。分治法是很多高效算法的基础,如排序算法(快速排序,归并排序),傅立叶变换(快速傅立叶变换)等等。
3. 组合步:组合步把各个子问题的解组合起来,它对分治算法的实际性能至关重要,算法的有效性很大地依赖于组合步的实现。
分治法的关键是算法的组合步。究竟应该怎样合并,没有统一的模式,因此需要对具体问题进行具体分析,以得出比较好的合并算法。
通常,在分析一个算法的计算复杂性时,一般将加法和乘法运算当作是基本运算来处理,即将执行一次加法或乘法运算所需的计算时间,看作一个仅仅取决于计算机硬件处理速度的常数。
然而,在有些情况下,需要处理数值很大的整数,这些数值无法在计算机硬件能直接表示的范围内进行处理。如果要精确地表示大整数的数值并在计算结果中要求精确地得到所有位数上的数字,就必须用软件的方法来实现大整数的算术运算,即用分治法实现大整数的运算。另外,分治法实现大整数运算,可以大大提高运算效率。
设两个n(na,nb)位d进制数A、B相乘:
当位数n为偶数时,将数拆分为两段等长的数段,高位段为H,低位段为L,则有
A=Ha*d^(n/2)+La B=Hb*d^(n/2)+Lb
当位数n为奇数时,可在数的首位前添0,使数的位数为偶数,然后将数拆分为两段等长的数段。
例如,计算2进制数1010与1110的乘积。步骤如下:
(1):1010=10*2^(2)+10 1110=11*2^(2)+10
(2):1010*1110=(10*2^(2)+10)*(11*2^(2)+10)=10*11*2^(4)+10*11*2^(2)+10*10*2^(2)+10*10
(3):1010*1110=(1*2^(1)+0)*(1*2^(1)+1)*2^(4)+(1*2^(1)+0)*(1*2^(1)+1)*2^(2)+(1*2^(1)+0)*(1*2^(1)+0)*2^(2)+(1*2^(1)+0)*(1*2^(1)+0)=2*3*16+2*3*4+2*2*4+2*2=140