减治法

减治技术利用了一种关系：一个问题给定实例的解和同样问题较小实例的解之间的关系。一旦建立了这样关系，我们既可以从顶至下（递归地），也可以从底至上（非递归地）地来运用。减至法有3种主要的变种：

在减变量变种中，每次算法迭代总是从实例规模中减去相同的常量。一般来讲，这个常量等于一（图4.1），但减二的情况发生在会根据实例的规模为奇数和偶数的不同情况，分别做不同的处理的算法中。

作为一个例子，计算a^n的值。规模为n的实例的解和规模为n－1的实例的解之间的关系，很明显a^n=a^(n-1)·a。所以函数f(n)=a^n既可以用它的递归定义

“从顶至下”地进行计算，也可以“从底至上”地把a自乘n-1次。5.1节~5.4节会给出减一算法的一些更令人感兴趣的例子。

减常因子技术意味着在算法的每次迭代中，总是从实例的规模中减去一个相同的常数因子。在大多数应用中，这样的常数因子等于二。图4.2描述的就是减半思想。

作为一个例子，再来看看指数问题。如果规模为n的实例计算的是a^n的值，规模减半的实例计算的就是a^(n/2)的值，它们之间有着明显的关系：n为偶数时，a^n=(a^(n/2)^2。如果n是奇数，我们必须先使用偶指数的规则来计算a^(n-1)，然后把结果乘以a。言而总之，我们得到了下列方程：

根据公式(4.2)递归计算a^n并且根据所做的乘法次数来度量该算法的效率，我们期望该算法属于O(log n)，因为，每次迭代时，问题的规模至少会减小一半。

注意该算法和基于分治思想的算法有所不同，分治算法对两个规模为n/2的指数问题实例分别求解：

a^n = a^⌊n/2⌋·a^⌈n/2⌉ , 如果n>1
a^n = a, 如果n=1

基于(4.2)的算法要比公式5.3的算法快得多。

5.5节给出了另外一些减常因子算法的例子。然而，这种算法的效率是如此之高，以至于这种类型的例子非常少。

最后，再减治法的减可变规模变种中，算法在每次迭代时，规模减小的模式都是不同的。计算最大公约数的欧几里得算法就是减可变规模的例子。这个算法是基于这个公式的：

gcd(m,n) = gcd(n, m mod n)

等号右边的那些参数既不是以常数也不是以常数因子的方式减小的。5.6节给出了这类算法的其他一些例子。