数据结构和算法18 之总结篇-阿里云开发者社区

开发者社区> 人工智能> 正文

数据结构和算法18 之总结篇

简介:

  前面介绍了经典的数据结构算法,这一节我们对这些数据结构和算法做一个总结,具体细节,请参见各个章节的详细介绍,这里我们用表格来呈现它们的效率。

1. 数据结构部分

数据结构中常用的操作的效率表

通用数据结构

查找 

插入 

 删除

遍历 

数组

O(N)

O(1)

O(N)

有序数组

O(logN)

O(N)

O(N)

O(N)

链表

O(N)

O(1)

O(N)

有序链表

O(N)

O(N)

O(N)

O(N)

二叉树

O(logN)

O(logN)

O(logN)

O(N)

二叉树(最坏)

O(N)

O(N)

O(N)

O(N)

红黑树

O(logN)

O(logN)

O(logN)

O(N)

2-3-4树

O(logN)

O(logN)

O(logN)

O(N)

哈希表

O(1)

O(1)

O(1)

专用数据结构

 

 

 

 

O(1)

O(1)

队列

O(1)

O(1)

优先级队列

O(N)

O(1)

优先级队列(堆)

O(logN)

O(logN)

 


2. 排序算法

常见的排序算法比较表

排序

平均情况

最好情况

最坏情况

稳定与否

空间复杂度

冒泡排序

O(N2)

O(N)

O(N2)

稳定

1

选择排序

O(N2)

O(N2)

O(N2)

不稳定

1

插入排序

O(N2)

O(N)

O(N2)

稳定

1

希尔排序

O(NlogN)

(依赖于增量序列)

不稳定

1

快速排序

O(NlogN)

O(NlogN)

O(N2)

不稳定

O(logN)

归并排序

O(NlogN)

O(NlogN)

O(NlogN)

稳定

O(N)

二叉树排序

O(NlogN)

O(NlogN)

O(N2)

稳定

O(N)

堆排序

O(NlogN)

O(NlogN)

O(NlogN)

不稳定

1

拓扑排序

O(N+E)

O(N)


        以上是对经典数据结构和算法部分的一个总结,如有错误之处,欢迎留言指正~


转载:http://blog.csdn.net/eson_15/article/details/51202049

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

分享:
人工智能
使用钉钉扫一扫加入圈子
+ 订阅

了解行业+人工智能最先进的技术和实践,参与行业+人工智能实践项目

其他文章