|
- UID
- 1029342
- 性别
- 男
|
最近看了一些关于算法思想的书，总结下。
数学归纳法
其实数学归纳法在算法设计上包括了很大的内容(让我见识到数学的重要性，当然我还是庆幸我喜欢数学)
我将数学归纳法分为两类：增量与划分。
一，增量：
很明显，增量就是和我们平时的数学归纳法一样，特殊点的就是
证明起始条件；假设对于K，证明成立；用假设去证明对K+1，证明成立
证明的重点就这如何利用‘K’证明‘(K+1)’
当然也可以认为是利用某种性质去推广
其实这个就是动态规划和贪心的基本性质，最优子结构性质以及重叠子问题性质(贪心选择性质)中的最优子结构性质；
现在举个"不同"例子 找多数元素(多数元素的定义：在给定有限个序列内，某元素的个数大于序列个数的1/2(比如 {1 2 3 3 3}中的3))
首先我们第一会想到枚举，很简单，时间复杂度为O(n^2)；最好的情况是一遍遍历就找到了:O(n) 最坏的情况是序列中没有多数元素：O(n^2) 平均情况:O(n^2)
现在让我们想下对于多数元素有什么性质，设序列元素个数为N，多数元素个数为m，
接下来给出一个很直接的性质(虽说很直接但是对我来说是不容易自己想出来的)：
性质1：删除序列中的两个不同的数，若存在多数元素，多数元素依然存在且不变。
现在我可以想出一个算法:
集合A:序列
循环：i：1->n-1
if(A==A[i+1]||A不存在) continue;
else delete A,A[i+1];
得到集合A`
很明显，集合A·中的元素一定相同
但是有个问题：集合中的元素不一定就是多数元素。
原因是性质1的前提是多数元素对于序列存在，我们可能会得到一个非法解
我们该怎么办，很简单，验证下最后得到的那个元素就行，
时间复杂度：O(n);
现在回过头看看我们的思路：
找到多数元素的性质，依次"增量"递减得到可能解，验证；
很明显找到性质是最关键的一步；
第二个例子，贪心；
双机调度问题：问题描述
给定n个作业，每个作业有两道工序，分别在两台机器上处理。一台机器一次只能处理一道工序，并且一道工序一旦开始就必须进行下去直到完成。
一个作业只有在机器1上的处理完成以后才能由机器2处理。假设已知作业i在机器j上需要的处理时间为t[i,j]。流水作业调度问题就是要求确定一个
作业的处理顺序使得尽快完成这n个作业。
分析下：
若只有一个作业(a,，b1),明显时间为a1+b1;
若有两个作业(a1,b1),(a2,b2);
若(a1,b1)在前，则有时间T12=a1+b1+a2+b2-min(a2,b1);
若(a2,b2)在前，则有时间T21=a2+b2+a1+b1-min(b2,a1);
有上可得时间为Tmin=a1+b1+a2+b2-max{min(a2,b1),min(a1，b2)};
由此我们可以得到一个贪心的性质，(a1,b1)和(a2,b2)中的元素若min(a2,b1)>=min(a1，b2)则(a1,b1)放在(a2,b2)前面；反之(a2,b2)放在(a1,b1)前面；
根据这个性质我们对作业进行排序即得到最优工作序列；
PS：由于个人表述能力不行，所以这个例子还有一些思考量，所以请大家自己用笔在纸上写下就可以得到一样的结论。
例外这个问题有个很优美的算法 Johnson算法，基本原理与上面类似，但是把结论做得更漂亮些了，有兴趣的可以去看下证明过程；
这里给出Johnson算法:
对给定的任务进行如下排序：
得到序列A：s1>=s1[j] 且以s1不减排序
序列B:s1<s2[j] 且以s2不增排序
最优调度即为A+B；
现在再回到数学归纳法上，回想如果我们得到K结论不足以证明“K+1”该怎么办？！
一个很常用的思想就是加强结论；
例三：最大连续子序列和问题
问题描述：给出序列A，求连续子序列和最大，我们定空序列为0；
下面直接给数学归纳法的(思考)过程：
设序列中元素个数为n
若序列中元素个数n为1，则最大子序列和为:A[1]>0?A[1]:0;
假设对于子序列"K"(前k个元素的子序列)，得到最大子序列S=“A...A[j]”(1<=i<=j<=k)
那么对于子序列"K+1",若S中的j=k+1，那么S'=S+A[k+1]>=S?S+A[k+1]:S;
若S中的j！=k+1，....
这个，我们该怎么办呢，关于最大子序列S与A[k+1]我们找不到更多的联系；
那么我们加强下论证结果，加入一个最大尾子序列和(包括当前序列尾节点的最大子序列)：S.end=“A[m]...A[k]”(1<=m<=k)
明显若S.end<0时，我们可以将S.end=0;
现在我们重新证明下；
设序列中元素个数为n
若序列中元素个数n为1，则最大子序列和为:A[1]>0?A[1]:0;最大尾子序列和为：0+A[1]>0?0+A[1]:0;
假设对于子序列"K"(前k个元素的子序列)，得到最大子序列S=“A...A[j]”(1<=i<=j<=k)
最大尾子序列S.end="A[m]...A[k]"(1<=m<=k)
那么对于子序列"K+1",最大子序列和为S>S.end+A[k]?S:S.end+A[k];
最大尾子序列和为S.end+A[k]>=0?S.end+A[k]:0;
这样就可以得到我们熟悉的时间复杂度为O(n)的最大子序列和算法了。
大家可以思考下，最大连乘子序列。
2，分治；
首先给出时间复杂度的主方法;
给出这个的目的是一种指引，对于设计算法的指引，通过这个你可以看到怎么样设计一个算法它的时间复杂度更低；
例子四，最近点对问题
问题描述：给出二维平面内若干个点的坐标，求出欧式距离最小的点对；
这个问题的算法有种分治版本并且网上的证明很多，我只是想给出它的简单思想；
首先对所有点进行排序，按照x递增的顺序排序；
1，二分排序后的点；两边的点数目大致相等(这只是奇偶数问题)
2，对两边点进行递归求解子最小点对距离len1，len2，直至点的数目<=3直接进行求解；
3，合并；
对于合并，如果我们枚举的话，根据上面的主方法得到时间复杂度为O(n^2)，这样还增加了问题的复杂性；
我们可以看到只有在划分线周围的点才可能比两边找到的子最近点对距离，
所以我们找到划分线两边距离d为min{len1，len2}的所有点；
若此时仍然枚举，时间复杂度还是为O(n^2);
接下来我就直接给出问题的正解，因为网上这类资料博客还是比较多的。
对于上一步得到的点，按照y不减排序，得到新的点序列，枚举每个点和每个点后6个的最小距离，更新最点点对距离；
根据主方法我们得到时间复杂度为O(nlogn)
就像之前说的主方法给我们一种指引在上面的例子展现得很好； |
|
