算法从入门到入土(一)

《我的第一本算法书》学习记录

数据结构

什么是数据结构

数据结构用于描述数据的顺序和位置关系，数据存储于计算机的内存中。内存如图所示，形似排成1列的箱子，1个箱子里存储1个数据。数据存储于内存时，决定了数据顺序和位置关系的便是“数据结构”。

数据结构

三种比较常见的存储格式：

全局无序随机排列（适合需要不断添加数据）
全局有序排列（不需要修改数据）
部分有序排列（两者合一）

链表

链表是数据结构之一，其中的数据呈线性排列。在链表中，数据的添加和删除都较为方便，就是访问比较耗费时间。

链表

这就是链表的概念图。Blue、Yellow、Red这3个字符串作为数据被存储于链表中。每个数据都有1个“指针”，它指向下一个数据的内存地址。

在链表中，数据一般都是分散存储于内存中的，无须存储在连续空间内。但是读取时需要按顺序读取，比如需要读取“red”就需要先从“Blue”读起。

在链表中添加数据只需要改变对应的指针指向的位置，将需要添加数据的位置前后的指针指向改变即可。

image

同时删除只需要将对应数据存储的指针取消即可，不需要删除实际数据，在正常运行过程中，数据会被后续结果覆盖。

image

复杂度：把链表中的数据量记成 $n$ 。访问数据时，我们需要从链表头部开始查找（线性查找），如果目标数据在链表最后的话，需要的时间就是 $O(n)$ ，添加数据或删除数据只需要该表指针位置，复杂度为 $O(1)$

如果在数据的结尾添加一个指针指向开始数据，就会构成循环列表，适用于固定数量的数据更新。

数组

数组也是数据呈线性排列的一种数据结构。与链表不同，在数组中，访问数据十分简单，而添加和删除数据比较耗工夫。

image

由于数据是存储在连续空间内的，所以每个数据的内存地址（在内存上的位置）都可以通过数组下标算出，我们也就可以借此直接访问目标数据（这叫作“随机访问”）。

复杂度： 假设数组中有n个数据，由于访问数据时使用的是随机访问（通过下标可计算出内存地址），所以需要的运行时间仅为恒定的 $O（1）$ 。向数组中添加新数据时，必须把目标位置后面的数据一个个移开。所以，如果在数组头部添加数据，就需要 $O（n）$ 的时间。

数组与列表的比较

	访问	添加	删除
链表	慢	快	快
数组	快	慢	慢

栈

栈也是一种数据呈线性排列的数据结构，不过在这种结构中，我们只能访问最新添加的数据。栈就像是一摞书，拿到新书时我们会把它放在书堆的最上面，取书时也只能从最上面的新书开始取。

入栈：往栈中添加数据的操作叫“入栈”（Push）

出栈：从栈中取出数据的操作叫“出栈”（POP）

image	image

从栈中取出数据时，是从最上面，也就是最新的数据开始取出的。

像栈这种最后添加的数据最先被取出，即“后进先出”的结构，我们称为Last In First Out，简称LIFO。与链表和数组一样，栈的数据也是线性排列，但在栈中，添加和删除数据的操作只能在一端进行，访问数据也只能访问到顶端的数据。想要访问中间的数据时，就必须通过出栈操作将目标数据移到栈顶才行。

队列

与前面提到的数据结构相同，队列中的数据也呈线性排列。虽然与栈有些相似，但队列中添加和删除数据的操作分别是在两端进行的。就和“队列”这个名字一样，把它想象成排成一队的人更容易理解。在队列中，处理总是从第一名开始往后进行，而新来的人只能排在队尾。

入队：往队列中添加数据的操作叫“入队”

出队：从队列中删除数据的操作叫“出队”

image	image

像队列这种最先进去的数据最先被取来，即“先进先出”的结构，我们称为First In FirstOut，简称FIFO。与栈类似，队列中可以操作数据的位置也有一定的限制。在栈中，数据的添加和删除都在同一端进行，而在队列中则分别是在两端进行的。队列也不能直接访问位于中间的数据，必须通过出队操作将目标数据变成首位后才能访问。

哈希表

哈希表存储的是由键（key）和值（value）组成的数据。例如，我们将每个人的性别作为数据进行存储，键为人名，值为对应的性别。

image

一般来说，我们可以把键当成数据的标识符，把值当成数据的内容。

操作：

计算key的哈希值
将得到的哈希值除以数组的长度，求得其余数
将key的数据存进对应余数号的箱子中
如果出现同样余数的情况，则称之为“冲突”，遇到这种情况，可使用链表在已有数据的后面继续存储新的数据。
存储完所有数据，哈希表也就制作完成

在存储数据的过程中，如果发生冲突，可以利用链表在已有数据的后面插入新数据来解决冲突。这种方法被称为“链地址法”。

除了链地址法以外，还有几种解决冲突的方法。其中，应用较为广泛的是“开放地址法”。这种方法是指当冲突发生时，立刻计算出一个候补地址（数组上的位置）并将数据存进去。如果仍然有冲突，便继续计算下一个候补地址，直到有空地址为止。可以通过多次使用哈希函数或“线性探测法”等方法计算候补地址。

在哈希表中，我们可以利用哈希函数快速访问到数组中的目标数据。如果发生哈希冲突，就使用链表进行存储。这样一来，不管数据量为多少，我们都能够灵活应对。如果数组的空间太小，使用哈希表的时候就容易发生冲突，线性查找的使用频率也会更高；反过来，如果数组的空间太大，就会出现很多空内容，造成内存的浪费。因此，给数组设定合适的空间非常重要。

堆

堆是一种图的树形结构，被用于实现“优先队列”（priority queues）。优先队列是一种数据结构，可以自由添加数据，但取出数据时要从最小值开始按顺序取出。在堆的树形结构中，各个顶点被称为“结点”（node），数据就存储在这些结点中。

image

结点内的数字就是存储的数据。堆中的每个结点最多有两个子结点。树的形状取决于数据的个数。另外，结点的排列顺序为从上到下，同一行里则为从左到右。
子结点必定大于父结点。因此，最小值被存储在顶端的根结点中。往堆中添加数据时，为了遵守这条规则，一般会把新数据放在最下面一行靠左的位置。当最下面一行里没有多余空间时，就再往下另起一行，把数据加在这一行的最左端。

当父结点的键值总是大于或等于任何一个子节点的键值时为最大堆。当父结点的键值总是小于或等于任何一个子节点的键值时为最小堆。

堆中最顶端的数据始终最小，所以无论数据量有多少，取出最小值的时间复杂度都为O（1）。

另外，因为取出数据后需要将最后的数据移到最顶端，然后一边比较它与子结点数据的大小，一边往下移动，所以取出数据需要的运行时间和树的高度成正比。假设数据量为n，根据堆的形状特点可知树的高度为log2n，那么重构树的时间复杂度便为O（logn）。

添加数据也一样。在堆的最后添加数据后，数据会一边比较它与父结点数据的大小，一边往上移动，直到满足堆的条件为止，所以添加数据需要的运行时间与树的高度成正比，也是O（logn）。

二叉查找树

二叉查找树（又叫作二叉搜索树或二叉排序树）是一种数据结构，采用了图的树形结构，数据存储于二叉查找树的各个结点中。

image

二叉查找树有两个性质：

第一个是每个结点的值均大于其左子树上任意一个结点的值。
第二个是每个结点的值均小于其右子树上任意一个结点的值。

往二叉查找树中添加数据：

从二叉查找树的顶端结点开始寻找添加数字的位置，小于它则往左移，大于它则往右移。

删除数据：

如果需要删除的结点没有子结点，直接删掉该结点即可。
如果需要删除的结点只有一个子结点，那么先删掉目标结点,然后把子结点移到被删除结点的位置上即可
如果需要删除的结点有两个子结点，那么先删掉目标结点,然后在被删除结点的左子树中寻找最大结点,最后将最大结点移到被删除结点的位置上。

比较的次数取决于树的高度。所以如果结点数为n，而且树的形状又较为均衡的话，比较大小和移动的次数最多就是log2n。因此，时间复杂度为O（logn）。但是，如果树的形状朝单侧纵向延伸，树就会变得很高，此时时间复杂度也就变成了O（n）。

排序

所谓排序

排序就是将输入的数字按照从小到大的顺序进行排列。

image	image

冒泡算法

冒泡排序就是重复“从序列右边开始比较相邻两个数字的大小，再根据结果交换两个数字的位置”这一操作的算法。在这个过程中，数字会像泡泡一样，慢慢从右往左“浮”到序列的顶端，所以这个算法才被称为“冒泡排序”。

image

在冒泡排序中，第1轮需要比较n-1次，第2轮需要比较n-2次……第n-1轮需要比较1次。因此，总的比较次数为（n-1）+（n-2）+…+1≈n2/2。这个比较次数恒定为该数值，和输入数据的排列顺序无关。不过，交换数字的次数和输入数据的排列顺序有关。假设出现某种极端情况，如输入数据正好以从小到大的顺序排列，那么便不需要任何交换操作；反过来，输入数据要是以从大到小的顺序排列，那么每次比较数字后便都要进行交换。因此，冒泡排序的时间复杂度为O（n2）。

选择算法

选择排序就是重复“从待排序的数据中寻找最小值，将其与序列最左边的数字进行交换”这一操作的算法。在序列中寻找最小值时使用的是线性查找。

image

选择排序使用了线性查找来寻找最小值，因此在第1轮中需要比较n-1个数字，第2轮需要比较n-2个数字……到第n-1轮的时候就只需比较1个数字了。因此，总的比较次数与冒泡排序的相同，都是（n-1）+（n-2）+…+1≈n2/2次。每轮中交换数字的次数最多为1次。如果输入数据就是按从小到大的顺序排列的，便不需要进行任何交换。选择排序的时间复杂度也和冒泡排序的一样，都为O（n2）。

插入排序

插入排序是一种从序列左端开始依次对数据进行排序的算法。在排序过程中，左侧的数据陆续归位，而右侧留下的就是还未被排序的数据。插入排序的思路就是从右侧的未排序区域内取出一个数据，然后将它插入到已排序区域内合适的位置上。

image

在插入排序中，需要将取出的数据与其左边的数字进行比较。就跟前面讲的步骤一样，如果左边的数字更小，就不需要继续比较，本轮操作到此结束，自然也不需要交换数字的位置。然而，如果取出的数字比左边已归位的数字都要小，就必须不停地比较大小，交换数字，直到它到达整个序列的最左边为止。具体来说，就是第k轮需要比较k-1次。因此，在最糟糕的情况下，第2轮需要操作1次，第3轮操作2次……第n轮操作n-1次，所以时间复杂度和冒泡排序的一样，都为O（n2）。和前面讲的排序算法一样，输入数据按从大到小的顺序排列时就是最糟糕的情况。

堆排列

堆排序的特点是利用了数据结构中的堆。

首先，在堆中存储所有的数据，并按降序来构建堆。从降序排列的堆中取出数据时会从最大的数据开始取，所以将取出的数据反序输出，排序就完成了。

堆排序一开始需要将n个数据存进堆里，所需时间为O（nlogn）。排序过程中，堆从空堆的状态开始，逐渐被数据填满。由于堆的高度小于log2n，所以插入1个数据所需要的时间为O（logn）。每轮取出最大的数据并重构堆所需要的时间为O（logn）。由于总共有n轮，所以重构后排序的时间也是O（nlogn）。因此，整体来看堆排序的时间复杂度为O（nlogn）。这样来看，堆排序的运行时间比之前讲到的冒泡排序、选择排序、插入排序的时间O（n2）都要短，但由于要使用堆这个相对复杂的数据结构，所以实现起来也较为困难。

归并排序

归并排序算法会把序列分成长度相同的两个子序列，当无法继续往下分时（也就是每个子序列中只有一个数据时），就对子序列进行归并。归并指的是把两个排好序的子序列合并成一个有序序列。该操作会一直重复执行，直到所有子序列都归并为一个整体为止。

image

归并排序中，分割序列所花费的时间不算在运行时间内（可以当作序列本来就是分割好的）。在合并两个已排好序的子序列时，只需重复比较首位数据的大小，然后移动较小的数据，因此只需花费和两个子序列的长度相应的运行时间。也就是说，完成一行归并所需的运行时间取决于这一行的数据量。看一下上面的图便能得知，无论哪一行都是n个数据，所以每行的运行时间都为O（n）。而将长度为n的序列对半分割直到只有一个数据为止时，可以分成log2n行，因此，总共有log2n行。也就是说，总的运行时间为O（nlogn），这与前面讲到的堆排序相同。

快速排序

快速排序算法首先会在序列中随机选择一个基准值（pivot），然后将除了基准值以外的数分为“比基准值小的数”和“比基准值大的数”这两个类别，再将其排列成以下形式。

[比基准值小的数] 基准值 [比基准值大的数]

接着，对两个“[ ]”中的数据进行排序之后，整体的排序便完成了。对“[ ]”里面的数据进行排序时同样也会使用快速排序。

image

快速排序是一种“分治法”。它将原本的问题分成两个子问题（比基准值小的数和比基准值大的数），然后再分别解决这两个问题。

子问题，也就是子序列完成排序后，再像一开始说明的那样，把他们合并成一个序列，那么对原始序列的排序也就完成了。不过，解决子问题的时候会再次使用快速排序，甚至在这个快速排序里仍然要使用快速排序。只有在子问题里只剩一个数字的时候，排序才算完成。像这样，在算法内部继续使用该算法的现象被称为“递归”。

如果数据中的每个数字被选为基准值的概率都相等，那么需要的平均运行时间为O（nlogn）

数组的查找

线性查找

线性查找是一种在数组中查找数据的算法。

image

检查数组中最左边的数字，将其与6进行比较。如果结果一致，查找便结束，不一致则向右检查下一个数字。

线性查找需要从头开始不断地按顺序检查数据，因此在数据量大且目标数据靠后，或者目标数据不存在时，比较的次数就会更多，也更为耗时。若数据量为n，线性查找的时间复杂度便为O（n）。

二分查找

二分查找也是一种在数组中查找数据的算法,它只能查找已经排好序的数据。

image

二分查找利用已排好序的数组，每一次查找都可以将查找范围减半。查找范围内只剩一个数据时查找结束。数据量为n的数组，将其长度减半log2n次后，其中便只剩一个数据了。也就是说，在二分查找中重复执行“将目标数据和数组中间的数据进行比较后将查找范围减半”的操作log2n次后，就能找到目标数据（若没找到则可以得出数据不存在的结论），因此它的时间复杂度为O（logn）。

图的搜索

什么是图

计算机科学或离散数学中说的“图”

image

上图中的圆圈叫作“顶点”（也叫“结点”），连接顶点的线叫作“边”。也就是说，由顶点和连接每对顶点的边所构成的图形就是图。

加权图	有向图
加权图	有向图

图的搜索指的就是从图的某一顶点开始，通过边到达不同的顶点，最终找到目标顶点的过程。根据搜索的顺序不同，图的搜索算法可分为“广度优先搜索”和“深度优先搜索”这两种。

广度优先搜索

广度优先搜索是一种对图进行搜索的算法。假设我们一开始位于某个顶点（即起点），此时并不知道图的整体结构，而我们的目的是从起点开始顺着边搜索，直到到达指定顶点（即终点）。在此过程中每走到一个顶点，就会判断一次它是否为终点。广度优先搜索会优先从离起点近的顶点开始搜索。

image

此处，候补顶点是用“先入先出”（FIFO）的方式来管理的，因此可以使用“队列”这个数据结构。

广度优先搜索的特征为从起点开始，由近及远进行广泛的搜索。因此，目标顶点离起点越近，搜索结束得就越快。

深度优先搜索

深度优先搜索和广度优先搜索一样，都是对图进行搜索的算法，目的也都是从起点开始搜索直到到达指定顶点（终点）。深度优先搜索会沿着一条路径不断往下搜索直到不能再继续为止，然后再折返，开始搜索下一条候补路径。

image

候补顶点是用“后入先出”（LIFO）的方式来管理的，因此可以使用“栈”这个数据结构。

深度优先搜索的特征为沿着一条路径不断往下，进行深度搜索。虽然广度优先搜索和深度优先搜索在搜索顺序上有很大的差异，但是在操作步骤上却只有一点不同，那就是选择哪一个候补顶点作为下一个顶点的基准不同。广度优先搜索选择的是最早成为候补的顶点，因为顶点离起点越近就越早成为候补，所以会从离起点近的地方开始按顺序搜索；而深度优先搜索选择的则是最新成为候补的顶点，所以会一路往下，沿着新发现的路径不断深入搜索。

贝尔曼-福特算法

贝尔曼-福特（Bellman-Ford）算法是一种在图中求解最短路径问题的算法。最短路径问题就是在加权图指定了起点和终点的前提下，寻找从起点到终点的路径中权重总和最小的那条路径。

image

将图的顶点数设为n、边数设为m，我们来思考一下贝尔曼-福特算法的时间复杂度是多少。该算法经过n轮更新操作后就会停止，而在每轮更新操作中都需要对各个边进行1次确认，因此1轮更新所花费的时间就是O（m），整体的时间复杂度就是 $O（nm）$

狄克斯特拉算法

与前面提到的贝尔曼-福特算法类似，狄克斯特拉（Dijkstra）算法也是求解最短路径问题的算法，使用它可以求得从起点到终点的路径中权重总和最小的那条路径路径。

image

将图的顶点数设为n、边数设为m，那么如果事先不进行任何处理，该算法的时间复杂度就是O（n2）。不过，如果对数据结构进行优化，那么时间复杂度就会变为 $O（m+nlogn）$ 。

总的来说，就是不存在负数权重时，更适合使用效率较高的狄克斯特拉算法，而存在负数权重时，即便较为耗时，也应该使用可以得到正确答案的贝尔曼-福特算法。

A*算法

A（A-Star）算法也是一种在图中求解最短路径问题的算法，由狄克斯特拉算法发展而来。狄克斯特拉算法会从离起点近的顶点开始，按顺序求出起点到各个顶点的最短路径。也就是说，一些离终点较远的顶点的最短路径也会被计算出来，但这部分其实是无用的。与之不同，A就会预先估算一个值，并利用这个值来省去一些无用的计算。

image

A*算法就是在Dijkstra算法的基础上添加一个人工预估距离

由人工预先设定的估算距离被称为“距离估算值”。如果事先根据已知信息设定合适的距离估算值，再将它作为启发信息辅助计算，搜索就会变得更加高效

如果我们能得到一些启发信息，即各个顶点到终点的大致距离（这个距离不需是准确的值）我们就能使用A*算法。

当然，有时这类信息是完全无法估算的，这时就不能使用A算法。距离估算值越接近当前顶点到终点的实际值，A算法的搜索效率也就越高；反过来，如果距离估算值与实际值相差较大，那么该算法的效率可能会比狄克斯特拉算法的还要低。如果差距再大一些，甚至可能无法得到正确答案。

不过，当距离估算值小于实际距离时，是一定可以得到正确答案的（只是如果没有设定合适的距离估算值，效率会变差）。

安全算法

传输数据时的四个问题

image	image	image	image
窃听	假冒	篡改	事后否认

窃听:A向B发送的消息可能会在传输途中被X偷看
假冒:A以为向B发送了消息，然而B有可能是X冒充的
篡改:即便B确实收到了A发送的消息，但也有可能像右图这样，该消息的内容在途中就被X更改了。
事后否认:B从A那里收到了消息，但作为消息发送者的A可能对B抱有恶意，并在事后声称“这不是我发送的消息”

解决这些问题的安全技术

问题和解决方法可以对应如下表格

问题	解决方法
窃听	加密
假冒	消息认证码 or 数字签名
篡改	消息认证码 or 数字签名
事后否认	数字签名

image	image

“数字签名”技术存在“无法确认公开密钥的制作者”这一问题。要想解决这个问题，可以使用“数字证书”技术。

加密的基础知识

我们需要给想要保密的数据加密。加密后的数据被称为“密文”。

收到密文后，需要解除加密才能得到原本的数据。把密文恢复为原本数据的操作就叫作“解密”。

在加密运算上会用到“密钥”。所以加密就是用密钥对数据进行数值运算，把数据变成第三者无法理解的形式的过程.

哈希函数

哈希函数可以把给定的数据转换成固定长度的无规律数值。转换后的无规律数值可以作为数据摘要应用于各种各样的场景。

输出的无规律数值就是“哈希值”。哈希值虽然是数字，但多用十六进制来表示。

哈希函数的特征

输出的哈希值数据长度不变
如果输入的数据相同，那么输出的哈希值也必定相同
即使输入的数据相似，但哪怕它们只有一比特的差别，那么输出的哈希值也会有很大的差异。输入相似的数据并不会导致输出的哈希值也相似
即使输入的两个数据完全不同，输出的哈希值也有可能是相同的，虽然出现这种情况的概率比较低。这种情况叫作“哈希冲突”
不可能从哈希值反向推算出原本的数据。输入和输出不可逆这一点和加密有很大不同
求哈希值的计算相对容易

哈希函数的算法中具有代表性的是MD5、SHA-1和SHA-2等。其中SHA-2是现在应用较为广泛的一个，

而MD5和SHA-1存在安全隐患，不推荐使用。不同算法的计算方式也会有所不同，比如SHA-1需要经过数百次的加法和移位运算才能生成哈希值。

共享密钥加密

共享密钥加密是加密和解密都使用相同密钥的一种加密方式。由于使用的密钥相同，所以这种算法也被称为“对称加密”

实现共享密钥加密的算法有凯撒密码、AES、DES、动态口令等，其中AES的应用最为广泛。

存在的问题:密钥可能被窃听

公开密钥加密

公开密钥加密是加密和解密使用不同密钥的一种加密方法。由于使用的密钥不同，所以这种算法也被称为“非对称加密”。加密用的密钥叫作“公开密钥”，解密用的叫作“私有密钥”。

实现公开密钥加密的算法有RAS算法、椭圆曲线加密算法等，其中使用最为广泛的是RSA算法。

存在的问题: 中间人攻击（man-in-the-middleattack）--通过中途替换公开密钥来窃听数据

混合加密

共享密钥加密存在无法安全传输密钥的密钥分配问题，公开密钥加密又存在加密解密速度较慢的问题。结合这两种方法以实现互补的一种加密方法就是混合加密。

该机制的主要过程为：先用非对称加密（计算复杂度较高）协商出一个临时的对称加密密钥（或称会话密钥），然后双方再通过对称加密算法（计算复杂度较低）对所传递的大量数据进行快速的加密处理。

混合加密在安全性和处理速度上都有优势。能够为网络提供通信安全的SSL协议也应用了混合加密方法。SSL是Secure Sockets Layer（安全套接层）的简写，该协议经过版本升级后，现在已正式命名为TLS（Transport Layer Security，传输层安全）。但是，SSL这个名字在人们心中已经根深蒂固，因此该协议现在也常被称为SSL协议或者SSL / TLS协议。

迪菲-赫尔曼密钥交换

迪菲-赫尔曼（Diffie-Hellman）密钥交换是一种可以在通信双方之间安全交换密钥的方法。这种方法通过将双方共有的秘密数值隐藏在公开数值相关的运算中，来实现双方之间密钥的安全交换。

image

根据素数P、生成元G和“GX mod P”求出X的问题就是“离散对数问题”，人们至今还未找到这个问题的解法，而迪菲-赫尔曼密钥交换正是利用了这个数学难题。

数学原理

消息认证码

消息认证码可以实现“认证”和“检测篡改”这两个功能。密文的内容在传输过程中可能会被篡改，这会导致解密后的内容发生变化，从而产生误会。消息认证码就是可以预防这种情况发生的机制。

由密钥和密文生成的值就是消息认证码，以下简称为MAC（Message Authentication Code）。

我们可以把MAC想象成是由密钥和密文组成的字符串的“哈希值”。计算MAC的算法有HMAC、OMAC、CMAC等。目前，HMAC的应用最为广泛。

数字签名

数字签名不仅可以实现消息认证码的认证和检测篡改功能，还可以预防事后否认问题的发生。由于在消息认证码中使用的是共享密钥加密，所以持有密钥的收信人也有可能是消息的发送者，这样是无法预防事后否认行为的。而数字签名是只有发信人才能生成的，因此使用它就可以确定谁是消息的发送者了。

数字证书

“公开密钥加密”和“数字签名”无法保证公开密钥确实来自信息的发送者。因此，就算公开密钥被第三者恶意替换，接收方也不会注意到。所以需要向认证中心（Certification Authority, CA）申请发行证书，证明公开密钥PA确实由自己生成。

数字证书就是像这样通过认证中心来担保公开密钥的制作者。这一系列技术规范被统称为“公钥基础设施”（Public Key Infrastructure, PKI）。

聚类

什么是聚类

聚类就是在输入为多个数据时，将“相似”的数据分为一组的操作。1个组就叫作1个“簇”。下面的示例中每个点都代表1个数据，在平面上位置较为相近、被圈起来的点就代表一类相似的数据。也就是说，这些数据被分为了3个簇。

image

k-means算法

k-means算法是聚类算法中的一种，它可以根据事先给定的簇的数量进行聚类。

算法步骤

首先准备好需要聚类的数据，然后决定簇的数量,本例中我们将簇的数量定为
随机选择3个点作为簇的中心点
计算各个数据分别和3个中心点中的哪一个点距离最近
将数据分到相应的簇中。这样，3个簇的聚类就完成了
计算各个簇中数据的重心，然后将簇的中心点移动到这个位置
重新计算距离最近的簇的中心点，并将数据分到相应的簇中
重复执行“将数据分到相应的簇中”和“将中心点移到重心的位置”这两个操作，直到中心点不再发生变化为止

image

k-means算法中，随着操作的不断重复，中心点的位置必定会在某处收敛，这一点已经在数学层面上得到证明。

除了k-means算法以外，聚类算法还有很多，其中“层次聚类算法”较为有名。与k-means算法不同，层次聚类算法不需要事先设定簇的数量。在层次聚类算法中，一开始每个数据都自成一类。也就是说，有n个数据就会形成n个簇。然后重复执行“将距离最近的两个簇合并为一个”的操作n-1次。每执行1次，簇就会减少1个。执行n-1次后，所有数据就都被分到了一个簇中。在这个过程中，每个阶段的簇的数量都不同，对应的聚类结果也不同。只要选择其中最为合理的1个结果就好。合并簇的时候，为了找出“距离最近的两个簇”，需要先对簇之间的距离进行定义。根据定义方法不同，会有“最短距离法”“最长距离法”“中间距离法”等多种算法。

其他算法

欧几里得算法

欧几里得算法（又称辗转相除法）用于计算两个数的最大公约数，被称为世界上最古老的算法。

image

素性测试

素性测试是判断一个自然数是否为素数的测试。素数（prime number）就是只能被1和其自身整除，且大于1的自然数。素数从小到大有2、3、5、7、11、13……目前在加密技术中被广泛应用的RSA算法就会用到大素数，因此“素性测试”在该算法中起到了重要的作用.

费马定理

网页排名

网页排名（PageRank，也叫作佩奇排名）是一种在搜索网页时对搜索结果进行排序的算法。

image