这些耳熟能详的算法你真的懂么

这些耳熟能详的算法你真的懂么

不知道你懂不懂,反正这李狗蛋我是当定了。对于很多比较经典的小算法,乍一听名字顿觉似曾相识兴奋不已,然而接下来大脑一片空白毫无头绪,只剩下那句永远的WTF回荡在脑海中。为了摆脱李狗蛋的囧境,笔者趁着闲来无事,研究了下几个出镜率较高的小算法,并基于pyhon完成其算法实现。

 1、归并排序 

归并排序算法是采用分治法的一个非常典型的应用,何谓分治,简单来讲就是化整为零,将大块拆成多个小块,分而治之。其算法原理是先把序列划分为n个子序列,然后对每个子序列排序,最后将子序列合并得到一个有序的最终序列。归并排序的算法我们通常用递归实现,先把待排序区间以中点二分,接着把左边子区间排序,再把右边子区间排序,最后把左区间和右区间用一次归并操作合并成有序的区间。

通过例子可以看到,如果序列的长度为n=8,拆分为子序列要经过8/2,4/2,2/2这三步,而每个子序列都要经过merge_sort,也就是要经过log8=3次,每次归并要经过的最大比较次数为n,则总计要比较nlogn次,所以归并排序的时间复杂度为O(nlogn)。归并排序不是就地排序即不是在原序列上进行的,而是最终产出一个长度为n的新序列,所以其空间复杂度为O(n)。归并排序比较占用内存,但却是一种效率高且稳定的算法,效率仅次于快速排序,稍后列举完几个排序算法之后会给出实际的对比数据供参考。

 2、快速排序 

快速排序也是分治法的应用算法之一。其原理是:首先选中一个基准值,一般为中间值,然后序列中的其他值与基准值做比较,小于基准值的放入一个数组A中,大于基准值的放入另一个数组B中,只要数组A和数组B是有序的,那么A+基准值+B则为最终的排好序的结果。

从示例中可以看到,快速排序也是需要不断的二等分,所以也需要递归logn个子序列,跟归并算法有点相似,但是由于每次都会抽取一个基准值,所以每个子序列需要比较n-1次(n表示子序列长度,时间复杂度计算中不作过细区分,而且忽视常量),所以快速排序的时间复杂度也是O(nlogn),但是效率是高于归并排序的,因为n值较小。

 3、冒泡排序 

冒泡排序原理:从第一个元素开始,依次比较相邻的两个元素,如果他们的顺序错误就把他们交换过来。对每一对相邻元素作同样的工作,从开始第一对到结尾的最后一对。经过这样的一遍比较,最后的元素应该会是最大的数。针对所有的元素重复以上的步骤,除了最后一个。持续每次对越来越少的元素重复上面的步骤,直到没有任何一对数字需要比较,也就是排序完成了。这个算法的名字由来是因为越大的元素会经由交换慢慢“浮”到数列的顶端,故名“冒泡排序”。

通过示例可以看到,要经过两层循环的比较,如果原序列是有序的话其时间复杂度为O(n),但这种情况比较少见,所以冒泡排序一般情况下的时间复杂度是O(n^2)。冒泡排序是就地排序,所以没有额外空间的消耗。但是冒泡排序每次遍历都需要做元素交换操作,这也就导致其排序效率比较低下。

 4、直接插入排序 

直接插入排序算法把要排序的数组分成两部分:第一部分包含了已排好序的数组A,而第二部分包含了无序的待插入元素的数组B。每次B中取一个元素,从右向左依次与数组A中的元素比较,直到找到合适位置,然后将该元素插入到A中,使A继续保持有序,如此往复,直到整个数组排序完成。

示例中可以看到也是两层循环,但是有条件限制l[i-1] > l[i],如果序列本身是有序的则只需要遍历n次,时间复杂度则为O(n);如果是无序的,当然这是普遍的情况,所以其普遍的时间复杂度为O(n^2)

 5、简单选择排序 

简单选择排序是最简单直观的一种算法,基本思想为每一趟从待排序的数据元素中选择最小(或最大)的一个元素作为首元素,经过多次遍历,直到所有元素排完为止。简单选择排序是不稳定排序。所谓的不稳定排序并不是说排序结果正确性的不稳定,判断是否为稳定排序的依据是排序前相邻的两个相等的元素,在排序后是否依旧相邻并且位置索引没有变化,即是否会有多余的交换操作,因为这对效率是会造成影响的。

由示例可见,简单排序也是双层循环,普遍情况下需要比较n^2次,所以其时间复杂度为O(n^2),但是交换操作次数最多为n次,这一点是要强于冒泡排序的。

关于排序的算法就列举这几个,接下来看下这几个排序算法的执行效率,先实现一个用于计时的装饰器用来统计运行时间

 6、二分查找 

二分查找也是采用分治策略的算法,采用二分查找的必要前提是保证序列是有序的,这点是非常重要的。其原理是将原序列从中间分为两个子序列A和B,并将中间值作为关键字与被查找的目标关键字做比较,如果相等则查找成功;如果目标值小于中间值,则从子序列A中查找;如果大于则从子序列B中查找。子序列的查找则重复上述过程直到目标命中。

二分查找每次都会将序列折中,然后在缩小范围后的子序列中查找,比如序列长度为n=8,目标值位于序列末尾,那么最多需要8/2, 4/2, 2/2三步就可以命中目标,可以看出有这样的关系2^3=8,需要的步数是以2为底数的log8=3,所以二分查找的时间复杂度为O(logn),其查找效率是非常高的,在长度为1024的序列中查找最多只需要10步,随着序列长度的增长,其相应的查找步数增速是很缓的。

示例中还列出了一种简单查找算法,简称傻找算法,就是从序列开头遍历比较,其时间复杂度是线性的O(n)。简单查找唯一的优势就是不需要序列是有序的,省去了排序的时间消耗。下面通过实际运行看下二者的效率差异

可以看到二分超找在查找效率上是有绝对优势的,当然例子中的序列是有序,如果数据量巨大排序也是比较耗时的。所以使用哪种算法还得看实际场景,毕竟脱离实际需求的技术都是耍流氓!

 7、斐波那契数列 

斐波那契数列指的是这样一个数列:1、1、2、3、5、8、13、21、34、…… 这个数列从第3项开始,每一项都等于前两项之和。原理很简单,但是斐波那契数列是有重大意义的,因为其在数学和生活以及自然界中都非常有用,可参考知乎上为何斐波那契数列如此重要,那家伙总结的老到位了,学渣渗入- -!关于斐波那契数列的实现方法,笔者提供了两种:

递归版的实现增加了缓存机制,避免大量重复的计算;python3默认的最大递归深度也就是操作栈数为1000,由于递归版的基线条件为n==1或n==2,在n值较大时递归的层级太大了还没有到达基线条件的话就会导致堆栈溢出,所以递归版的先修改了操作栈数的最大值。通过下边的实际输出,可以看到两种版本的运行效率相差无几。
 这里再补充一个利用标准库functools中的lru_cache实现的带缓存的递归版本

说点什么

avatar
  订阅  
提醒