分治法与主定理
分治法
分治法是种经典的算法设计策略,这种策略简单来说就是先把原问题分成规模更小的子问题,再把子问题划分成更小的子问题…一直划分到子问题十分容易解决,然后就能倒过来解决原问题。数学中数列项的递推式就能看做是基于分治策略的算法,数学中的递推式很多时候都比通项式更容易找到和理解,分治算法相对于一些其他的算法很多时候也是这样。虽然分治策略本身不限定算法的物理实现形式,但通常默认分治算法是递归函数程序。
由于分支策略只是一个大的设计框架,所以不同问题的分治算法间的区别可以很大,且同一问题也可能有多种分治算法。但所有分治算法都是遵循如下3大步骤的(或者说能按这几大步骤设计):
1) 分解子问题:需要拆分出几个子问题,这些子问题的输入应该怎么求得;
2) 解决子问题:解决上述这些子问题,并得到子问题的解;… 阅读全文