对各种算法的初步认识1
稍微看了一下青岛二中的讲义，初步对各种算法有了一定的认识，由于是大体看了一眼，肯定有不少错误
1、普里姆最小花费生成树
首先是图示：
对于这图，很容易看出，假设N=(V,E)是一个连通的网。
生成的最小生成树为T=(V,TE)，求T的步骤如下：
1.初始化：U={u0}，TE={φ}。
2.在所有u∈U，v∈V-U的边(u,v)∈E中，找一条权最小的边(u0,v0)，TE+{(u0,v0)}→TE，{v0}+U→U。3.如果U=V最后得到最小生成树T=，其中TE为最小生成树的边集，则算法结束；否则重复2。
连通网有邻接矩net表示。若两个顶点之间不存在边，其权值为计算机内允许最大值；否则为对应边上的权值。
发现其规律为：每次从生成树T到T外的所有边中，找出一条最小边。
当然这样每次找啊找找的时间复杂度为O(k(n-k))。还是有些浪费的样子。
针对优化，若每次在生成之前，将每个点的最短边放入集合中，然后判断是否能连通，若不能连通择寻找第二小的边。我初步是这么想的，但是也不排除这是局部最优解的问题，因为每次选的点未必一样的样子，回头会仔细看的。
2、基数排序
首先这个排序对数据范围有比较严格的要求，MS根据范围不同取的关键字也是不一样的
就0～99来讨论吧
首先令L＝{a0,a1,a2.......an}是具有n个元素的链表
当然在这里n只能等于10
其中的关键字分别从0～9共10个
按照排序数据的取个位，分别存入相应关键字的链表
然后取十位按照顺序放入，写到这里，我突然想到，实际不用那么麻烦
对于数据范围的问题，只是依次从低向高取位然后存入相应链表的操作而已
若数据为n位那么就要取n次的样子～
简单的演示
一共有10个数据，依次为99 78 12 56 65 23 4 8 66 10
第一次链表情况
a0={10}
a1=∮
a2={12}
a3={23}
a4={4}
a5={65}
a6={56,66}
a7=∮
a8={78,8}
a9={99}
在第二遍取第二低位的关键字时，要把关键字的链表串起来查询，因为此时个位已经有序
第二次链表情况
a0={4,8}
a1={10,12}
a2={23}
a3=∮
a4=∮
a5={56}
a6={65,66}
a7={78}
a8=∮
a9={99}
然后将关键字联起来，就是4,8,10,12,23,56,65,66,78,99，此时已经排序完成
代码实现不是十分困难，就是需要细心。
时间复杂度为O(n)
3，贪心，背包
一般会出典型的装箱问题，箱子空间大小为N，有M个价值不等的物体，问装入后剩余空间最小为多少
这种东西想弱点无论什么数都输出0不就得了？问题是没这么弱的
所以一般都是按照价值大小排序，然后依次用箱子的剩余空间减去物体价值，若小于0，择放弃该物体选择下一价值较小物体，一直到没法选择或箱子剩余空间已经为0
4，模拟算法
就是模拟一些实际动作，没有很大的技巧，细心细心再细心，注意一些常识性问题
例如生日日数
CCC老师的生日是YY年MM月DD日，他想知道自己出生后第一万天纪念日的日期（出生日算第0天）。
不难看出直接模拟是绝对可行的，此时存在的问题就是闰年的判断，每月的天数
那么这样就很简单了
首先判断闰年，返回一个布尔类型的数据
然后判断月的天数，如果到了2月，根据判断闰年的布尔类型的数据判断是否为29天或28天
开始加，判断是否已经超出12月，若是，就往下加1年，一直加到10000天以后
输出结果