数学技术之算法概论篇(6)
⑤当今世界最受人们重视的十大经典算法
当今世界，已经被发现或创造的经典算法数不胜数。如果，一定要你投票选出你最看重的十大算法，你会作何选择?2011年，有人在Stack Exchange上发起了提问，向网友们征集当今世界最为经典的十大算法。众人在一大堆入围算法中进行投票，最终得出了呼声最高的以下十个算法。鉴于其中多数算法前面已在不同的地方分别介绍过，这里从略。不过希望网友明白一点，以下票选出来的十大算法，受票选领域所限，不等同于、也绝非就是当今世界最为经典的十大算法，如许多常用的数值型经典算法并不在列等。
第一名：Union-find 合并操作和查询算法;
第二名：Knuth-Morris-Pratt字符串匹配算法;
第三名：BFPRT 算法;
第四名： Quick sort 快速排序算法 ;
第五名：Floyd-Warshall all-pairs 最短路径算法;
第六名：Gentry’s Fully Homomorphic Encryption Scheme 绅士完全同态加密机制算法;
第七名：Depth First Search、Breadth First Search 深度、广度优先搜索算法;
第八名：Miller-Rabin 作的类似的试验测试算法;
第九名：Binary Search 二分查找算法;
第十名：Huffman coding 霍夫曼编码算法。
⑥程序员应知道的10大基础算法
这里总结出的《程序员应知道的10大基础算法》，包含排序、查找、搜索和分类等几类算法，当然是程序员应当知道的一些基础算法，但是不是“程序员应知道的10大基础算法”，可能是仁者见仁、智者见智，不同看法一定很多。因其数量极其有限，既不可能全面，更不可能完善，只能是仅供参考而已。
算法一：快速排序算法
快速排序是由东尼·霍尔所发展的一种排序算法。在平均状况下，排序 n 个项目要Ο(nlogn)次比较。在最坏状况下则需要Ο(n 2 )次比较，但这种状况并不常见。事实上，快速排序通常明显比其他Ο(n log n) 算法更快，因为它的内部循环可以在大部分的架构上很有效率地被实现出来。快速排序使用分治法策略来把一个串行分为两个子串行，再分别进行排序。
算法步骤：
1 从数列中挑出一个元素，称为 “基准”。
2 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面。在这个分区退出之后，该基准就处于数列的中间位置，称为分区操作。
3 递归地把小于基准值元素的子数列和大于基准值元素的子数列排序。
递归的最底部情形，是数列的大小是零或一，也就是都已经被排序好了。虽然一直递归下去，但是这个算法总会退出，因为在每次的迭代中，它至少会把一个元素摆到它最后的位置上去。
算法二：堆排序算法
堆排序(Heap sort)是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于(或者大于)它的父节点。
堆排序的平均时间复杂度为Ο(nlogn) 。
算法三：归并排序算法
归并排序(Merge sort)是建立在归并操作上的一种有效的排序算法。该算法是分治法的一个非常典型的应用。
算法步骤：
1. 申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列;
2. 设定两个指针，最初位置分别为两个已经排序序列的起始位置;
3. 比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置;
4. 重复步骤3直到某一指针达到序列尾;
5. 将另一序列剩下的所有元素直接复制到合并序列尾。
算法四：二分查找算法
二分查找算法是一种在有序数组中查找某一特定元素的搜索算法。搜索过程从数组的中间元素开始，如果中间元素正好是要查找的元素，则搜索过程结束;如果某一特定元素大于或者小于中间元素，则在数组大于或小于中间元素的那一半中查找，而且跟开始一样从中间元素开始比较。如果在某一步骤数组为空，则代表找不到。这种搜索算法每一次比较都使搜索范围缩小一半。折半搜索每次把搜索区域减少一半，时间复杂度为Ο(nlogn) 。
算法五：线性查找算法 BFPRT
BFPRT算法解决的问题十分经典，即从某n个元素的序列中选出第k大(或第k小)的元素，通过巧妙的分析，BFPRT可以保证在最坏情况下仍为线性时间复杂度。该算法的思想与快速排序思想相似，当然，为使得算法在最坏情况下，依然能达到o(n)的时间复杂度，算法作者对此做了精妙的处理。
算法六：深度优先搜索算法 DFS
深度优先搜索算法(Depth First Search)，是搜索算法的一种。它沿着树的深度遍历树的节点，尽可能深的搜索树的分支。当节点v的所有边都己被探寻过，搜索将回溯到发现节点v的那条边的起始节点。这一过程一直进行到已发现从源节点可达的所有节点为止。如果还存在未被发现的节点，则选择其中一个作为源节点并重复以上过程，整个进程反复进行直到所有节点都被访问为止。DFS属于盲目搜索。
深度优先搜索是图论中的经典算法，利用深度优先搜索算法可以产生目标图的相应拓扑排序表，利用拓扑排序表可以方便的解决很多相关的图论问题，如最大路径问题等等。一般用堆数据结构来辅助实现DFS算法。
深度优先遍历图算法步骤：
1. 访问顶点v;
2. 依次从v的未被访问的邻接点出发，对图进行深度优先遍历;直至图中和v有路径相通的顶点都被访问;
3. 若此时图中尚有顶点未被访问，则从一个未被访问的顶点出发，重新进行深度优先遍历，直到图中所有顶点均被访问过为止。
算法七：广度优先搜索算法 BFS
广度优先搜索算法(Breadth First Search)，是一种图形搜索算法。简单的说，BFS是从根节点开始，沿着树(图)的宽度遍历树(图)的节点。如果所有节点均被访问，则算法中止。BFS同样属于盲目搜索。一般用队列数据结构来辅助实现BFS算法。
算法步骤：
1. 首先将根节点放入队列中;
2. 从队列中取出第一个节点，并检验它是否为目标。如果找到目标，则结束搜寻并回传结果，否则将它所有尚未检验过的直接子节点加入队列中;
3. 若队列为空，表示整张图都检查过了——亦即图中没有欲搜寻的目标。结束搜寻并回传“找不到目标”;
4. 重复步骤2。
算法八：Dijkstra算法
戴克斯特拉算法(Dijkstra’s algorithm)是由荷兰计算机科学家艾兹赫尔·戴克斯特拉提出。迪科斯彻算法使用了广度优先搜索解决非负权有向图的单源最短路径问题，算法最终得到一个最短路径树。该算法常用于路由算法或者作为其他图算法的一个子模块。
算法九：动态规划算法
动态规划(Dynamic programming)是一种在数学、计算机科学和经济学中使用的算法，通过把原问题分解为相对简单的子问题的方式求解一些复杂的问题。 动态规划常常适用于有重叠子问题和最优子结构性质的问题，动态规划方法所耗时间往往远少于朴素解法。
动态规划背后的基本思想非常简单。大致上，若要解一个给定问题，我们需要解其不同部分(即子问题)，再合并子问题的解以得出原问题的解。 通常许多子问题非常相似，为此动态规划法试图仅仅解决每个子问题一次，从而减少计算量：一旦某个给定子问题的解已经算出，则将其记忆化为存储，以便下次需要同一个子问题解之时直接查表。 这种做法在重复子问题的数目关于输入的规模呈指数增长时特别有用。动态规划最经典的问题当属背包问题。
算法步骤：
1. 最优子结构性质。如果问题的最优解所包含的子问题的解也是最优的，我们就称该问题具有最优子结构性质(即满足最优化原理)。最优子结构性质为动态规划算法解决问题提供了重要线索。
2. 子问题重叠性质。子问题重叠性质是指在用递归算法自顶向下对问题进行求解时，每次产生的子问题并不总是新问题，有些子问题会被重复计算多次。动态规划算法正是利用了这种子问题的重叠性质，对每一个子问题只计算一次，然后将其计算结果保存在一个表格中，当再次需要计算已经计算过的子问题时，只是在表格中简单地查看一下结果，从而获得较高的效率。
算法十：朴素贝叶斯分类算法
分类是将一个未知样本分到几个预先已知类别的过程。在众多的分类模型中，应用最为广泛的两种分类模型是决策树模型(Decision Tree Model)和朴素贝叶斯模型(Naïve Bayesian Model，NBC)。决策树模型通过构造树来解决分类问题。首先利用训练数据集来构造一棵决策树，一旦树建立起来，它就可为未知样本产生一个分类。在分类问题中使用决策树模型有很多的优点，决策树便于使用，而且高效;根据决策树可以很容易地构造出规则，而规则通常易于解释和理解;决策树可很好地扩展到大型数据库中，同时它的大小独立于数据库的大小;决策树模型的另外一大优点就是可以对有许多属性的数据集构造决策树。决策树模型也有一些缺点，比如处理缺失数据时的困难，过度拟合问题的出现，以及忽略数据集中属性之间的相关性等。
朴素贝叶斯分类算法是一种基于贝叶斯定理的简单概率分类算法。贝叶斯分类的基础是概率推理，就是在各种条件的存在不确定、仅知其出现概率的情况下，如何完成推理和决策任务。概率推理是与确定性推理相对应的。而朴素贝叶斯分类器是基于独立假设的，即假设样本每个特征与其他特征都不相关。
朴素贝叶斯分类器依靠精确的自然概率模型，在有监督学习的样本集中能获取得非常好的分类效果。在许多实际应用中，朴素贝叶斯模型参数估计使用最大似然估计方法，换言之朴素贝叶斯模型能工作并没有用到贝叶斯概率或者任何贝叶斯模型。尽管是带着这些朴素思想和过于简单化的假设，但朴素贝叶斯分类器在很多复杂的现实情形中仍能够取得相当好的效果。
|
