课程咨询 :186-8884-0703

深圳Web培训 > 达内新闻 > 程序员必知的算法(1)
  • 程序员必知的算法(1)

    发布:深圳Web培训      来源:达内新闻      时间:2016-03-07

  • 程序员必知的算法(1)

    算法一:BFPRT(线性查找算法)

    BFPRT算法解决的问题十分经典,即从某n个元素的序列中选出第k大(第k小)的元素,通过巧妙的分析,BFPRT可以保证在最坏情况下仍为线性时间复杂度。该算法的思想与快速排序思想相似,当然,为使得算法在最坏情况下,依然能达到o(n)的时间复杂度,五位算法作者做了精妙的处理。

    算法步骤:

    1.将n个元素每5个一组,分成n/5(上界)组。

    2.取出每一组的中位数,任意排序方法,比如插入排序。

    3.递归的调用selection算法查找上一步中所有中位数的中位数,设为x,偶数个中位数的情况下设定为选取中间小的一个。

    4.用x来分割数组,设小于等于x的个数为k,大于x的个数即为n-k。

    5.若i==k,返回x;若ik,在大于x的元素中递归查找第i-k小的元素。

    终止条件:n=1时,返回的即是i小元素。

    算法二:朴素贝叶斯分类算法

    朴素贝叶斯分类算法是一种基于贝叶斯定理的简单概率分类算法。贝叶斯分类的基础是概率推理,就是在各种条件的存在不确定,仅知其出现概率的情况下,如何完成推理和决策任务。概率推理是与确定性推理相对应的。而朴素贝叶斯分类器是基于独立假设的,即假设样本每个特征与其他特征都不相关。

    朴素贝叶斯分类器依靠精确的自然概率模型,在有监督学习的样本集中能获取得非常好的分类效果。在许多实际应用中,朴素贝叶斯模型参数估计使用最大似然估计方法,换言之朴素贝叶斯模型能工作并没有用到贝叶斯概率或者任何贝叶斯模型。

    尽管是带着这些朴素思想和过于简单化的假设,但朴素贝叶斯分类器在很多复杂的现实情形中仍能够取得相当好的效果。

    算法三:快速排序算法

    快速排序是由东尼·霍尔所发展的一种排序算法。在平均状况下,排序n个项目要Ο(n log )次比较。在最坏状况下则需要Ο(n2)次比较,但这种状况并不常见。事实上,快速排序通常明显比其他Ο(n log n)算法更快,因为它的内部循环(inner loop)可以在大部分的架构上很有效率地被实现出来。

    快速排序使用分治法(Divide and conquer)策略来把一个串行(list)分为两个子串行(sub-lists)。

    程序员必知的算法(1)

    算法步骤:

    1从数列中挑出一个元素,称为“基准”(pivot),

    2重新排序数列,所有元素比基准值小的摆放在基准前面,所有元素比基准值大的摆在基准的后面(相同的数可以到任一边)。在这个分区退出之后,该基准就处于数列的中间位置。这个称为分区(partition)操作。

    3递归地(recursive)把小于基准值元素的子数列和大于基准值元素的子数列排序。

    递归的最底部情形,是数列的大小是零或一,也就是永远都已经被排序好了。虽然一直递归下去,但是这个算法总会退出,因为在每次的迭代(iteration)中,它至少会把一个元素摆到它最后的位置去。

    算法四:归并排序

    归并排序(Merge sort,台湾译作:合并排序)是建立在归并操作上的一种有效的排序算法。该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。

    算法步骤:

    1.申请空间,使其大小为两个已经排序序列之和,该空间用来存放合并后的序列

    2.设定两个指针,最初位置分别为两个已经排序序列的起始位置

    3.比较两个指针所指向的元素,选择相对小的元素放入到合并空间,并移动指针到下一位置

    4.重复步骤3直到某一指针达到序列尾

    5.将另一序列剩下的所有元素直接复制到合并序列尾

    算法五:BFS(广度优先搜索)

    广度优先搜索算法(Breadth-First-Search),是一种图形搜索算法。简单的说,BFS是从根节点开始,沿着树(图)的宽度遍历树(图)的节点。如果所有节点均被访问,则算法中止。BFS同样属于盲目搜索。一般用队列数据结构来辅助实现BFS算法。

    算法步骤:

    1.首先将根节点放入队列中。

    2.从队列中取出第一个节点,并检验它是否为目标。

    如果找到目标,则结束搜寻并回传结果。

    否则将它所有尚未检验过的直接子节点加入队列中。

    3.若队列为空,表示整张图都检查过了——亦即图中没有欲搜寻的目标。结束搜寻并回传“找不到目标”。

    4.重复步骤2。

    希望以上对你将你有所帮助!达内深圳WEB前端培训有着国内首家完整的移动WEB开发课程体系,高度专注WEB前沿技术。达内深圳WEB培训开发项目全部来自于真实的企业项目,单独项目代码量超过 6万行。为了让学员尽快的进入到企业开发的项目中,达内使用自主开发的产品和为客户定制的企业产品为案例,大批深圳达内WEB培训开发学员都从中收益。

    我们是 一群热爱IT的年轻人,如果你也爱IT、爱WEB开发,欢迎前来达内深圳WEB培训中心参观学习,让我们共同为梦想发声。

上一篇:达内集团全体员工为学员张嘉乐父亲捐善款

下一篇:程序员必知的算法(2)

最新开班日期  |  更多

WEB前端工程师--全日制班

WEB前端工程师--全日制班

开班日期:3月31日

WEB培训前端工程师--周末班

WEB培训前端工程师--周末班

开班日期:3月31日

WEB培训免费训练营一期

WEB培训免费训练营一期

开班日期:3月31日

WEB培训免费训练营二期

WEB培训免费训练营二期

开班日期:3月31日

  • 地址:深圳市福田区八卦四路华晟达(原南方苑)大厦4楼东—深圳WEB开发培训中心
  • 课程培训电话:186-8884-0703     全国服务监督电话:400-827-0010
  • 服务邮箱 ts@tedu.cn
  • 2001-2016 达内时代科技集团有限公司 版权所有 京ICP证8000853号-56