找回密码
 立即注册
  • QQ空间
  • 回复
  • 收藏

算法时间复杂度整理

admin 2019-9-16 06:06 91人围观 C++相关

数据结构与算法分析,在我从事开发工作一来就一直很抵触接触,很烧脑,也很难理解,可能自己的基础还没有到,最近又重新研究了一下,感觉并没有起初的那样晦涩难懂了。



排序算法的执行效率受下面几个因素影响

1、最好、最坏、平均情况时间复杂度

2、时间复杂度的系数、常数、低阶

3、比较次数和交换(或移动)次数

排序算法的内存消耗

得法的内存消耗可以通过空间复杂度来衡量

针对排序算法的空间复杂度,引入新概念,原地排序Sorted in place,指空间复杂度为0(1)的排序算法

排序算法的稳定性

稳定性:如果待排序的值存在相同元素,经过排序后相同元素之间原有顺序不变

不稳定性:顺序改变的称为不稳定的排序算法

下面分析一下时间复杂度为0(n的平方)的算法

1、冒泡排序

因为使用双重for循环来遍历数据,只会操作相邻的两个数据

空间复杂度0(1)

前后顺序不变,原地排序算法,稳定排序算法

时间复杂度最好0(n)最坏0(n的平方)

2、插入排序

和冒泡一样使用双重for循环实现,和冒泡不同的是插入排序会在未排序的数组中取出一位与已排序数据进行比较(元素比较、元素移动),如果需要插入时,先把有序数据统一后移,然后再插入,因为插入排序只做一次赋值,所以效率会比冒泡好很多。

属于原地排序算法,稳定排序算法

时间复杂度最好0(n)最坏0(n的平方)

3、选择排序

Selection Sort选择排序,空间复杂度为0(1),原地排序

时间复杂度最好0(1)最坏0(n的平方)

与冒泡、插入排序相比有什么不同?

选择排序是不稳定的排序算法,选择未排序的最小值,并和前面的数据交换,破坏了稳定性

文章从来不只是用来阅读的,需要我们通过阅读来深入思考,我喜欢使用“why how what”的方法来分析问题,本篇只是一个小小的介绍,还需要用心的你下来具体思考分析一下,必要时去网上查阅更多的资料来探索发现,一起努力吧


----------------------------------------------------------------------------------------------------------------------
我们尊重原创,也注重分享,文章来源于微信公众号:追梦人之路,建议关注公众号查看原文。如若侵权请联系qter@qter.org。
----------------------------------------------------------------------------------------------------------------------

鲜花

握手

雷人

路过

鸡蛋

yafeilinux和他的朋友们微信公众号二维码

微信公众号

专注于Qt嵌入式Linux开发等。扫一扫立即关注。

Qt开源社区官方QQ群二维码

QQ交流群

欢迎加入QQ群大家庭,一起讨论学习!

我有话说......