【技术小火车】万万没想到!原来你是这样的算法君?!

据说算法正在统治世界?吓得我瓜子都掉了......好吧无稽之谈,你们的神之蔑视脸我先收下了,谁让人家单纯无邪天真可爱说啥信啥呢。别闹了,赶紧言归正传(严肃脸)。虽然没有那么可怖,但是算法的作用自然不必多说。毕竟无论男男女女老老少少,想在计算机这条道路上走得更远,算法都是不可或缺的。

然而算法千千万,又有哪些算法属于“夜空中的那颗星”呢?本文就带领大家驰骋算法世界,为你展现丰富而又独特的算法之美。简言之嘛,就是咱们一起攻略新副本去!那走着?走啥走,赶紧飞吧!前方一大波福利来袭,千万要Hold住哦。

1.由插入排序看如何分析和设计算法

算法的作用自然不用多说,就像编程语言中的“Hello World!”一般,算法学习中第一步便是拿下排序算法。扑克牌玩过不?撇开部分人不说,相信大部分童鞋都热衷于将牌按序号排排好。那么这其中就蕴含着算法的思想:1.手中的扑克牌有2种可能:没有扑克牌(为空)或者有扑克牌且已排好序。2.从桌上抓起一张牌后,从左往右(从右往左)依次进行比较,最终选择一个合适的位置插入。

简单的说,插入排序的精髓在于“逐个比较”。

关于算法的分析也有两个定义:1.输入规模,当考虑的是排序算法时,那么规模就指的是项数;如果考虑的是图算法,那么规模就是顶点数和边数。2.运行时间,名义上来说就是算法执行的时间,但实际上我们在分析一个算法时考量的算法执行的操作数或步数。

关于渐近记号、设计分治算法、分析分治算法、递归和迭代等内容咱就不一一赘述了。

2.由股票收益问题再看分治算法和递归式

如前所述,分治算法三步走:divide、conquer、combine,可以自行通过多个小算法来深化对分治算法的理解哦:二分查找算法、平方算法、斐波那契数以及平方递归算法等。

下面我们探讨一个最大子数组问题。股票,经久不衰的热门话题,那么就由此引入来进一步学习分治算法。举个栗子,股票价格如下所示:

不过嘛,比起股票价格咱们更应该关注价格波动。如果将这个波动定义为数组A,那么问题就转换为寻找A的和最大的非空连续子数组。这种连续子数组就是标题中的最大子数组(maximum subarray)。So可以将原表简化如下:

在这个算法中,常常被说成是“一个最大子数组”而不是“最大子数组”,因为可能有多个子数组达到最大和。

那么使用分治思想解决问题、分析分治算法和渐近记号中的省略问题、借助递归树求解递归式的内容我们也就爽快跳过吧,感兴趣的自己戳去。

3.由招聘问题看随机算法

又是一年招聘季,在这里我们就来当个Boss过把瘾(Yeah)。假如某天,你想雇用一名算法工程师......相信一看大家就知道重点是什么了:费用必须最低。那么解决这个问题的逻辑呢,当然就是:1.从1到n个应聘者中不断地面试;2.如果当前应聘者比上一个更好,则雇用当前应聘者并解雇上一个雇用者。

如果大家理解了上面的描述,那就相当于理解了最坏情况分析。在这个算法中,我们显然不可能每次都去强制控制它的输入,因此便有了随机算法这么一说。所谓随机算法,就是使用排列的顺序随意。选取一个主元,输入的顺序便不重要了。无论所提供的输入是递增排序还是递减排序,亦或是没有排序,都对算法没有影响。我们都会将其打乱,让它们随机分布。

既然选择了这个算法,自然有它挡不住的优点:

1.它的运行时间不依赖于输入序列的顺序;

2.无需对输入序列的发布做任何假设;

3.无论是怎样的输入都不会引发最差的运行情况;

4.而最差的情况却是由随机数产生器决定的。

那么什么样的算法是随机的呢?其行为不仅由输入决定,而且也有随机数生成器产生的数值决定,这种算法就是随机的。

4.五张图带你体会堆算法

What is堆?堆是一类特殊的数据结构的统称,通常被看作一棵树的数组对象。在队列中,调度程序反复提取队列中的第一个作业并运行,因为实际情况中某些时间较短的任务却可能需要等待很长时间才能开始执行,或者某些不短小、但很重要的作业,同样应当拥有优先权。而堆就是为了解决此类问题而设计的数据结构。

二叉堆是一种特殊的堆,是完全二叉树或者近似完全二叉树,满足堆特性:父节点的键值总是保持固定的序关系于任何一个子节点的键值,且每个节点的左子树和右子树都是一个二叉堆。当父节点的键值总是大于任何一个子节点的键值时为最大堆,当父节点的键值总是小于或等于任何一个子节点的键值时为最小堆。为了更加形象,可以借用带数字的圆圈和线条来表示二叉堆等,但其实都是用数组来表示的。如果根节点在数组中的位置是1,第n个位置的子节点则分别在2n和2n+1位置上。

所以,我们可以:

1.通过MAX-HEAPIFY维护最大堆;

2.通过BUILD-MAX-HEAP构建最大堆;

3.通过HEAPSORT进行堆排序算法。

5.传说中的快排是怎样的

下面咱们来见识下传说中可遇不可求的快速排序(英文名:Quicksort,也作划分交换排序)。快排是一个高效的排序算法,当情况良好时它可以比主要竞争对手的归并排序和堆排序快上大约两三倍。这也是一个分治算法,而且就在原地排序。

所谓原地排序,就是指在原来的数据区域内进行重排,就像插入排序一般。而归并排序就不一样,它需要额外的空间来进行归并排序操作。为了在线性时间与空间内归并,它不能在线性时间内实现就地排序,原地排序对它来说并不足够。而快速排序的优点就在于它是原地的,也就是说它很节省内存。

通过诸多实践童鞋们是不是也发现了:快速排序的运行时间依赖于Partition过程,也就是依赖于划分是否平衡,而归根结底这还是由于输入的元素决定的。

  •   如果划分是平衡的,那么快速排序算法性能就和归并排序一样。
  •   如果划分是不平衡的,那么快速排序的性能就接近于插入排序。

6.比较排序之外学习新的线性时间排序

通过前面的介绍肯定好多小伙伴顿悟了“在排序的最终结果中,各元素的次序依赖于它们之间的比较”。于是乎,这类排序算法被统称为”比较排序“。比较排序是通过一个单一且抽象的比较运算(比如“小于等于”)读取列表元素,而这个比较运算则决定了每两个元素中哪一个应该先出现在最终的排序列表中。典型的比较排序有:插入排序、选择排序、归并排序、堆排序、快速排序。此外,还有一些非典型性的比较排序:Intro sort、冒泡排序、奇偶排序、双向冒泡排序等。

那么线性时间排序有哪些呢?

1.计数排序:计数排序(counting sort)的思路很简单,就是确定比x小的数有多少个。严谨来讲,计数排序是一个根据比较键值大小的排序算法,它也是个整数排序算法。它通过比较对象的数值来操作,并通过这些计数来确定它们在即将输出的序列中的位置。运行时间是线性的且取决于最大值和最小值之间的差异,当值的变化明显大于数目时就不太适用了。

2.基数排序:基数排序(radix sort)是一个古老的算法,用于卡片排序机上。它可以使用前面介绍的计数排序作为子程序,然而它并不是原址排序。因此当数据过大而内存不太够时,使用它并不是一个明智的选择。

3.桶排序:这倒是一个有趣的算法了,它充分利用了链表的思想。

7.分不清栈和队列?一张图给你完整体会

栈?队列?是不是傻傻分不清了(蚊香眼)?往往容易弄混的就是“后进先出”和“先进先出”了。那么,关于栈和队列下面就直接列出相关操作的伪代码咯。

STACK-EMPTY(S)
1   if S.top==0
2       return TRUE
3   else
4       return FLASE
PUSH(S,k)
1   S.top=S.top+1
2   S[S.top]=x
POP(S)
1   if STACK-EMPTY(S)
2       error "underflow"
3   else
4       S.top=S.top-1
5   return S[S.top+1]

队列

ENQUEUE(Q,x)
1   Q[Q.tail]=x
2   if Q.tail==Q.length
3       Q.tail=1
4   else
5       Q.tail=Q.tail+1
DEQUEUE(Q)
1   x=Q[Q.head]
2   if Q.head=Q.length
3       Q.head=1
4   else
5       Q.head=Q.head+1
6   return x

8.图文搭配诠释三种链表及其哨兵

链表是什么呢?它和前面的栈和队列一般,都是基本的数据结构,其中的各个对象按线性顺序排列。链表主要包括:单向链表、双向链表、循环链表。

我们来研究下不同的链表是如何指引的?

  •  单链表中有一个关键字key和指针next,将链表中的一个元素设为x,那么x.key就是它的值,x.next就是链表的后继元素。如果x.next=NIL,那么就说明没有后继元素了,因此x就是链表的尾(tail)。
  •  双向链表对比单链表,无非就是多了一个前驱,用x.prev来表示。同样的,x.prev=NIL,表示没有前驱,那么x就是链表的头(head)。而如果头都为空了,那么整个链表也就是空的了。
  •  循环链表是双向链表的升级版,就是将链表尾部的元素x的next指向链表的头部y,元素头部的元素y的prev指向链表的尾部x。

关于链表的搜索、插入、删除等问题就不一一说明啦。

既然提到了哨兵,我们也来分析下。哨兵节点常常被用在链表和遍历树中,它并不拥有或引用任何被数据结构管理的数据。常常用哨兵节点来代替null,这样的好处有以下3点:

1.增加操作的速度

2.降低算法的复杂性和代码的大小

3.增加数据结构的鲁棒性

简而言之,哨兵就是为了简化边界条件的处理而存在滴。



Si不Si看得不过瘾?赶快来戳下方详情链接吧!

【算法】1 由插入排序看如何分析和设计算法:

【算法】2 由股票收益问题再看分治算法和递归式:

【算法】3 由招聘问题看随机算法:

【算法】4 五张图带你体会堆算法:

【算法】5 传说中的快排是怎样的:

【算法】6 比较排序之外学习新的线性时间排序:

【算法】7 分不清栈和队列?一张图给你完整体会:

【算法】8 图文搭配诠释三种链表及其哨兵:

时间: 2016-11-04

【技术小火车】万万没想到!原来你是这样的算法君?!的相关文章

马化腾:从技术小角色到.COM公敌

      从"技术小角色"到".COM公敌" 淘宝网新推出不到一个月的收费服务"招财进宝"的夭折,引发了马云和马化腾的一番口水大战. "这一年半以来,我们承受了无数的压力和明枪暗箭",也许是感慨万千,马云直接将矛头对准了马化腾."我自己认为挖人很累,互联网同行竞争应该遵守一定的游戏规则,光靠挖人很难做到创新.而现在腾讯拍拍网最大的问题就是没有创新,所有的东西都是抄来的." "马化腾是业内有名的抄

本以为灰指甲已经治好,没想到停药后更加严重

本以为灰指甲已经治好,没想到停药后更加严重 5年前,夏先生感染了灰指甲,2011年底他选择哈尔滨乐泰药业的"亮甲"进行治疗.经过一年多的治疗,花费了一万多元,灰指甲终于没了,夏先生停下药准备观察一段时间.谁知过了两个月,情况恶化了,刚刚变成粉嫩的新指甲,又变回了灰指甲. 不忍心拔指甲,选择亮甲治疗 2007年,夏先生发现自己左右手各有两个指甲,长得较其它指甲突出厚重,且颜色发灰,他意识到自己可能是感染上了灰指甲.听说灰指甲是真菌感染所致,夏先生担心传染给家人,于是开始四处用药治疗灰指甲

普京创造的五个没想到让中国人震惊

普京执政以来,尽管执政的模式是国家资本主义加资源资本主义,但是在关乎人民生活的这个基本问题上,普京的执政理念却是马克思恩格幻想的共产主义模式.研究俄罗斯问题的人,对普京的执政理念,总结了五个没有想到: 第一个没想到是住房不要钱:"在俄罗斯居民住房不收费,人均18平方米以下的部分无偿转给个人,18 平方米以上部分也只收很少的钱." 第二个没想到是用水没水表:用于日常生存所必需的"自来水.热水(一天24小时供应).供暖,从来就不收费,索性连水表都省了." 第三个没想到看

问题-刚开始学习java ,自己写了一个聊天小程序,没报错但是有毛病,希望能帮忙问一下

问题描述 刚开始学习java ,自己写了一个聊天小程序,没报错但是有毛病,希望能帮忙问一下 刚开始学习java ,自己写了一个聊天小程序,没有报任何错误.测试时打开3个聊天小窗口 A,B,C,在A中输入文字,只在B中显示出来了,而且显示出了三句相同语句.查了好几个小时都没有查出来,希望高手能帮帮忙,看看是怎么回事,并且告诉我是通过什么方法找出来的. 以下是客户端和服务器端代码 客户端: import java.awt.*; import java.awt.event.*; import java

技术小故事-Activity的Launch Mode引起的动画“疑案”

 前两天同事在做我们的App注册页面的的时候碰到了这样的一个场景:在注册过程中有这样的一个流程,进入页面(Activity)A,完成输入,再进入页面 B,完成输入,最后在进入页面C:即A->B->C.现在问题来了,在 C 中有一个验证逻辑:如果验证成功直接从C挑战到A,同时要干掉B :如果验证失败,则从 C 中可以依次次back到B到A,同事问我有没有好点的办法?我告诉他可以去看看 Activity 的 Launch Mode 这部分知识看看能不能解决问题.  过一会儿,他又带着新问题过来了:

漫画图解IT人最在乎的三样东西,没想到运维狗又中枪了

中国有逾千万的IT从业人员 大家经常戏称他们为"挨踢"人 那么这些人群有些什么痛点呢? 看看下面三组漫画吧 01 关于女朋友 02 关于工资 03 关于时间 据说IT人22点下班都算早的 其中又以运维汪加班最为严重 但是! 品高云V7.0隆重推出 深度自动化运维服务 平台可根据预设的运维方案和常用指令 自动执行运维功能 充分解放运维压力 每天按时下班不用愁 下面就来看看怎样部署吧 深度分析品高云V7.0 05 深度自动化运维 云计算时代 IT 运维的发展趋势 目前,云计算已经从概念阶段

哎~大学期间自学javaee没想到公司都不太认可自学

问题描述 无奈-没有项目经验怎么办? 解决方案 解决方案二: 解决方案三:找实习单位

技术大牛带你走向机器学习“正道”:小朋友才迷信算法,大人们更重视工程实践

雷锋网按:"算法"这两字在人工智能圈已然成为"高大上"的代名词,由于不少在校生和职场新人对它的过度迷恋,多名 AI 资深人士均对这一现象表示担忧.李开复曾这样说到: 现在的 AI 科学家大部分是在科研环境中培养出来的,不但欠缺工程化.产品化的经验,而且对于错综复杂的商业环境也并不熟悉,更缺乏解决实际问题所必须的数据资源. 随着开源框架层出不穷,人工智能产品化和商业化进程不断加速,使得算法的门槛逐渐降低,但对工程的要求不断在提高.这种情况下,实际应用和工程能力基础扎实

阿里巴巴风鸣:做技术Leader要有危机意识

真是不知道.在阿里巴巴集团安全部竟然有这么一对儿,像极了"史密斯夫妇".唯一的不同是,今天咱们要开八这一对儿是写代码的,电影中的那对儿是玩枪的. 风鸣,钱盾反诈平台iOS技术开发的负责人.戴眼镜,白白净净,说话不紧不慢,显年轻,关键是头发浓密而且发质很好,与我印象中的不太一样,感觉是程序员界的一股"清流". 当我问他是不是还单身的时候,得到的是非常决绝的回答--已婚了!而他的另一半,竟然也在阿里安全.这爆料,让我有点措手不及. 虽然,夫妻档在阿里巴巴不仅不罕见,而且