程序设计方法与实践-变治法

变换之美

变治法就是基于变换的思路，进而使原问题的求解变得简单的一种技术。

变治法一般有三种类型：

实例化简：将问题变换为同问题，但换成更为简单、更易求解的实例。
改变表现：变化为同实例的不同形式，而这个形式还会比较好解决。
问题化简：将原问题变化成另问题实例，而这个问题的解决方案已知。

预排序（Presorting）

预排序的思想基于，当列表有序的时候，所有的操作将会变得更加简单。

检查元素的唯一性

如果是一个带查找序列是无序的，那么想要检查数列中的元素是不是唯一的，使用蛮力法的时间复杂度肯定是 $\Theta \left ( n^{2} \right )$ 的。

那如果用一个高效的排序算法 $\Theta \left ( n\log n \right )$ 对待查列表进行排序，那么列表有序之后在进行元素唯一性检查，时间复杂度将会变成线性的，那么总体的时间复杂度就会是 $\Theta \left ( n\log n \right )$ 。

伪码描述：

//先做预排序
sort(A[0,...n-1]);//基于预排序的元素唯一性检查
PresortElementUniqueness(A[0,...n-1]){for(int i=0; i<n-1; i++){if(A[i]==A[i+1])return FALSE;}return TRUE;
}

模式计算（computer a mode）

模式计算简单说就是，找到一个列表中出现次数最多的元素。同样我们先考虑一下使用蛮力法去解决这个问题，最坏输入就是列表中没有相同的元素，那么每个元素i都要与剩下的i-1个元素进行比较，然后作为一个新的元素存入辅助列表中。

时间复杂度是： $T\left ( n \right )=0+1+2+....n-1=\left ( n-1 \right )n/2$

而如果当待查列表是有序的，就只需要线性遍历一遍列表，然后不断去更新那个元素连续出现的次数最多，所以时间复杂度就由原来的平方降低成了对数级别。

伪码描述：

//预排序
sort(A[0,...n-1])//基于预排序的模式计算
PresortingComputerMode(A[0,...n-1]){int modefrequence=0;int modeValue=0;int runlength=0;int runValue=0;for(int i=0; i<n-1; i++){runlength=1; runValue=A[i];while(i+runlength < n-1 && A[i+runlength]==A[i]){runlength++;}if(runlength > modefrequence) modefrequence=runlength modeValue=A[i];i=i+runlength;}return modeValue;
}

这里注意虽然看起来是二重循环，但是实际上时间复杂度是线性的。

查找问题

我们知道，查找问题中比较优的算法是折半查找 $\Theta \left ( \log n \right )$ ，但是使用折半查找的前提是列表有序。这了大家就会问了，不管待查列表是有序的还是无序的，查找问题的时间复杂度都是 $\Theta \left ( n \right )$ 的。那么此时先预排序 $\Theta \left ( n\log n \right )$ ，再进行折半查找，这不是画蛇添足了吗？

但其实大家想一想在现实的场景中，查找往往不是执行一次的操作，而是频繁执行的，而预排序是永久起作用的。所以当查找操作次数的规模较大时，预排序的优势就会渐渐显现出来。

这里有几道习题给到大家：

这道题比较有意思，能够很好地了解预排序在输入规模比较大时的优势。解决这个问题可以利用不等式： $n\log n+k\log_{2} n<=kn/2$

所以有， $k>=\left (n\log n \right )/\left ( n/2-\log _{2} n\right )$ 当 $n=1000$ 时， $k_{min}=21$ 。

会对预排序的优势有更好的的理解。

伪码描述：

//分治法求数列最大值最小值
MaxMin(A[l,...r],Max,Min){if(r-l==1){if(A[l]>A[r]) Max=A[l]else Min=A[r]}else{MaxMin(A[l,...(l+r)/2],Max1,Min1)MaxMin(A[(l+r)/2,...r],Max2,Min2)if(Max1<Max2) Max=Max2if(Min1>Min2) Min=Min2   }
}

平衡查找树-AVL树

查找树是一种典型的实现字典的数据结构。
查找树中的所有元都来自于待查列表集合，并且，左子树的结点元素都小于子树根节点元素，而右子树都大于它。
将集合改写成一个二叉查找树，就是一种典型的“改变形式”的方法。

而基于第二点性质，最优情况下使用二叉查找树的效率为 $\Theta \left ( \log n \right )$ ，但是在最差情况下其时间复杂度会退化为 $\Theta \left ( n \right )$ ，也就是这个二叉树可能极不平衡。

AVL树是一个二叉查找树，并且给每一个顶点定义一个平衡因子（只能取0、1.-1），也就是该结点左子树与右子树的高度差（空树的高度差定义为-1）。
而当要插入一个结点时，该二叉树会失去平衡，那么就要进行旋转，使得该二叉树再次平衡。

不平衡时的旋转情况：

根结点的左子树增加一个左子树上加一个结点使得不平衡（即插入1）时

将连接根节点和它右子树的边进行右旋：

根结点的右子树的右子树增加一个结点使得不平衡（即插入3）时

将连接根结点和右子树的边进行左旋：

根结点左子树的右子树上加一个结点使得不平衡：

进行左右旋：

根结点的右子树的左子树加上一个结点使得不平衡：

进行右左旋：

上面是比较简单的例子，下面看一下实际中较为复杂的例子：

毫无疑问的是，这种情况属于，在根结点的左子树的右子树上加上一个结点使得不平衡。所以我要进行左右旋：

比较麻烦的一点是如何处理，T1和T3，但其实只要仔细分析还是比较容易的。我们已应该利用好二叉查找树的性质，也就是左子树上的结点都小于根结点，右子树上的结点都大于它。则，T1上的结点都大于c，所以只能挂在c的右子树上；同理，T3都小于r，所以只能挂在r的左子树上。

最后再给出一道题给大家思考：

依次插入：5、6、8、3、2、4、7

答案参考：

堆和堆排序

堆的性质

堆是一种满二叉树
并且堆中的每个结点，都大于它的左右结点

堆的构造

自底向上：

先构造一个满二叉树，按顺序放置键值。
然后从最后的双亲结点开始，检查是否满足堆的性质2，若不满足则将该双亲结点与最大的子结点交换。一直到根结点。

以bottom-up为例，

伪码描述：

//使用自底向上构造堆
HeapBottom-up(H[1,...n]){for(int i=n/2; i>=1; i++){k=i; v=H[i]; heap=false;  //判断以当前结点为根结点的树是不是堆的标志while(!heap && 2*k<=n){int j=2*k;if(j<n){if(H[j]<=H[j+1]) j++;}if(H[k]>H[j]){H[k]=H[j];k=j;}else{heap=true;}} //whileH[k]=v;} //for
}

过程详解：

最后的双亲结点，也就是7，检查是否满足。不满足，则交换7和8：

然后从右往左继续找，也就是9，检查是否满足。满足，则继续找2，不满足则交换2和9：

但是因为9的位置发生了变化，所以要检查原先9的位置是否依旧满足条件。2显然不满足条件，则交换2和6：

自顶向下

将包含新键值K的新结点插入最后一个叶子结点后面。
然后按照相同的方法调整位置。

过程详解：

例如现在需要插入新键值10，则将其与父母结点比较，8比10要小，所以应该交换位置：

然后继续检查，更新后会受影响的父母结点，也就是9，同样9小于10，所以要交换位置：

如此便完成了新键值的插入。

此时有同学可能会问，为什么要费这么大功夫去做这件事呢？这里还是要考虑堆的重要性质：任意结点一定大于它的左右字结点。

堆的删除

堆的删除大致分为两步：

将堆的最大键值删除，就是让其与最后一个叶结点交换。
将堆的规模-1，然后再次进行堆化。

堆排序

所以总结就是，堆排序的步骤：

将待排序数组，构造成堆
然后删除堆的最大键值
规模-1，继续堆化，并重复

删除的顺序即为降序顺序。

时间效率分析：

霍纳法则

$p\left ( x \right )=a_{n}x^{n}+a_{n-1}x^{n-1}...a_{1}x+a_{0}$

一个多项式的表达式如上，如果我想要在计算机中去储存这些系数，并且完成这些计算，其实是比较困难的。可能人脑，看这些比较简单，但是这形式用编程解决并不容易。于是采用变治法去思考，我们将其转换成另一种形式：

$p\left ( x \right )=\left ( ...\left ( a_{n}x+a_{n-1} \right )x... \right )x+a_{0}$

你可能会说，这种形式看起来很别扭，而且有点多此一举，但是这计算机看来，这种形式是最方便做计算的了。

通过一个观察下面实例，不难发现规律：

在计算机中，一旦过程可以被重复，就可以用循环解决。

伪码描述：

Horner(p[0,...n]){int p = p[n], x;  //设变量p，并输入xfor(int i=n-1; i>=0; i--){p = p*x + p[i];}return p;
}

时间复杂度： $\Theta \left ( n \right )$

二进制幂

基于“改变形式”的思想，使用指数n的二进制表示，来计算 $a^{n}$ :

从左往右计算二进制串（利用霍纳法则）

首先将指数n表示为比特串： $n=b_{l}2^{l}+...b_{1}2^{1}+b_{0}$

所以就将形式转化为了： $a^{n}=a^{p\left ( 2 \right )}=a^{b_{l}2^{l}+...b_{1}2^{1}+b_{0}}$

而这个形式也就是我们熟悉的，利用霍纳法则求解多项式值的形式。

伪码描述：

L_RBExp( a, b[n] ){int product = a;for(int i=n-1; i>=0; i--){product *=product;if(!b[i]){      product *=a;  //这一步大家要仔细看一下}}
}

从右往左计算二进制串

$a^{b_{l}2^{l}+...b_{1}2^{1}+b_{0}}=a^{b_{l}2^{l}}*...a^{b_{1}2^{1}}*a^{b_{0}}$

也就是将其化为乘积的形式。

伪码描述：

R_LBExp( a,b[n] ){term = a;if(b[0]==1) product = a;else product = 1;for(int i=1; i<=n; i++){term *=term;if(!b[1]) pruduct *=term;}return product;
}

上面就是变治法的一些主要内容，然后还有一个比较重要的一个知识点就是高斯消元法，我还没有梳理好，之后会更新。