精彩牛耳,用心缔造

排序算法之时间空间复杂度分析

作者: 编辑: 来源: 发布日期: 2019.07.03
信息摘要:
排序算法,就是如何使得记录按照要求排列的方法。排序算法在很多领域得到相当地重视,尤其是在大量数据的处理方面。一个优秀的算法可以节省大量的资源…

排序算法,就是如何使得记录按照要求排列的方法。排序算法在很多领域得到相当地重视,尤其是在大量数据的处理方面。一个优秀的算法可以节省大量的资源,今天我们一起来了解下几种排序算法的时间空间复杂度。

1、冒泡排序不管序列是怎样,都是要比较n(n-1)/2次的,最好、最坏、平均时间复杂度都为O(n²),需要一个临时变量用来交换数组内数据位置,所以空间复杂度为O(1)。有很多人说冒泡排序的最优的时间复杂度为O(n),其实这是在代码中使用一个标志位来判断是否已经排序好的,是冒泡排序的优化版,如果元素已经排序好,那么循环一次就直接退出。

2、选择排序是冒泡排序的改进,同样选择排序无论序列是怎样的都是要比较n(n-1)/2次的,最好、最坏、平均时间复杂度也都为O(n²),需要一个临时变量用来交换数组内数据位置,所以空间复杂度为O(1)。

3、插入排序不同,如果序列是完全有序的,插入排序只要比较n次,无需移动时间复杂度为O(n),如果序列是逆序的,插入排序要比较O(n²)和移动O(n²),所以平均复杂度为O(n²),最好为O(n),最坏为O(n²),排序过程中只要一个辅助空间,所以空间复杂度O(1)。

4、快速排序的时间复杂度最好是O(nlogn),平均也是O(nlogn),最坏情况是序列本来就是有序的,此时时间复杂度为O(n²),快速排序的空间复杂度可以理解为递归的深度,而递归的实现依靠栈,平均需要递归logn次,所以平均空间复杂度为O(logn)。

5、归并排序需要一个临时temp[]来储存归并的结果,空间复杂度为O(n),时间复杂度为O(nlogn),可以将空间复杂度由O(n)降低至O(1),然而相对的时间复杂度则由O(nlogn)升至O(n²)。

6、希尔排序的时间复杂度分析及其复杂,有的增量序列的复杂度至今还没人能够证明出来,只需要记住结论就行,{1,2,4,8,...}这种序列并不是很好的增量序列,使用这个增量序列的时间复杂度(最坏情形)是O(n²),Hibbard提出了另一个增量序列{1,3,7,...,2^k-1},这种序列的时间复杂度(最坏情形)为O(n^1.5),Sedgewick提出了几种增量序列,其最坏情形运行时间为O(n^1.3),其中最好的一个序列是{1,5,19,41,109,...},需要一个临时变量用来交换数组内数据位置,所以空间复杂度为O(1)。

7、堆排序的时间复杂度,主要在初始化堆过程和每次选取最大数后重新建堆的过程,初始化建堆时的时间复杂度为O(n),更改堆元素后重建堆的时间复杂度为O(nlogn),所以堆排序的平均、最好、最坏时间复杂度都为O(nlogn),堆排序是就地排序,空间复杂度为常数O(1)。

8、基数排序对于n个记录,执行一次分配和收集的时间为O(n+r),如果关键字有d位,则要执行d遍,所以总的时间复杂度为O(d(n+r))。该算法的空间复杂度就是在分配元素时,使用的桶空间,空间复杂度为O(r+n)=O(n)

牛耳推荐资讯
牛耳成长故事丨你是我见过的最差的学生,也是最好的学生

牛耳成长故事丨你是我见过的最差的学生,也是最好的学生

第一次见到小陈,是在我们教学楼的了楼梯口,他一边吃着包子嘴里还停的念叨着:“糟糕了,第一天上课就迟到,早餐也没吃完,太倒霉了。”当时我看到这个学生的时候心里就在想:”这不会是我们校区的学生吧?“第二次见到小陈,是在咨询办公室里。他一个人关着门在咨询老师的办公室里,身体还斜靠在椅子,手机放着很大......
2020-05-15
做好这四件事,线上学习依然可以高效

做好这四件事,线上学习依然可以高效

一场突如其来的疫情似乎让一切放慢了脚步,开学时间延迟,但是“延迟不延学”,深圳、广州、武汉、杭州、北京,湖北、云南、江苏……疫情期间,全国20多省市,通过腾讯教育为学校搭建在线课堂。目前,已有百万教师使用腾讯教育在线课堂,助力数千万学生“不停学”。不仅如此,钉钉更是因为线上教学的原因“惨遭一星好......
2020-05-14
长沙Java培训-长沙Java培训学校

长沙Java培训-长沙Java培训学校

长沙Java培训班与企业停止专业对口的项眼关作,帮助学生挑前顺应严重剧烈的计算机工程设计,把实际常识的教育与实践项眼的展开融为一体,使得学习效力更高。按照长沙Java培训机构讲授品质凹凸比较是比较专业的,由于不但针对长沙Java培训学校的讲授方面,还摸清了各家培训机构的教育重点方向。长沙Java培训学校课程安......
2020-05-08

咨询热线

400-0731-162
  
    • *

    • *