每个程序员都应该收藏的算法复杂度速查表-阿里云开发者社区

开发者社区> 知与谁同> 正文

每个程序员都应该收藏的算法复杂度速查表

简介:
+关注继续查看

算法复杂度这件事

这篇文章覆盖了计算机科学里面常见算法的时间和空间的大 OBig-O 复杂度。我之前在参加面试前,经常需要花费很多时间从互联网上查找各种搜索和排序算法的优劣,以便我在面试时不会被问住。最近这几年,我面试了几家硅谷的初创企业和一些更大一些的公司,如 Yahoo、eBay、LinkedIn 和 Google,每次我都需要准备这个,我就在问自己,“为什么没有人创建一个漂亮的大 O 速查表呢?”所以,为了节省大家的时间,我就创建了这个,希望你喜欢!

--- Eric 

图例

绝佳 不错 一般 不佳 糟糕

数据结构操作

数据结构 时间复杂度 空间复杂度
  平均 最差 最差
  访问 搜索 插入 删除 访问 搜索 插入 删除  
Array O(1) O(n) O(n) O(n) O(1) O(n) O(n) O(n) O(n)
Stack O(n) O(n) O(1) O(1) O(n) O(n) O(1) O(1) O(n)
Singly-Linked List O(n) O(n) O(1) O(1) O(n) O(n) O(1) O(1) O(n)
Doubly-Linked List O(n) O(n) O(1) O(1) O(n) O(n) O(1) O(1) O(n)
Skip List O(log(n)) O(log(n)) O(log(n)) O(log(n)) O(n) O(n) O(n) O(n) O(n log(n))
Hash Table - O(1) O(1) O(1) - O(n) O(n) O(n) O(n)
Binary Search Tree O(log(n)) O(log(n)) O(log(n)) O(log(n)) O(n) O(n) O(n) O(n) O(n)
Cartesian Tree - O(log(n)) O(log(n)) O(log(n)) - O(n) O(n) O(n) O(n)
B-Tree O(log(n)) O(log(n)) O(log(n)) O(log(n)) O(log(n)) O(log(n)) O(log(n)) O(log(n)) O(n)
Red-Black Tree O(log(n)) O(log(n)) O(log(n)) O(log(n)) O(log(n)) O(log(n)) O(log(n)) O(log(n)) O(n)
Splay Tree - O(log(n)) O(log(n)) O(log(n)) - O(log(n)) O(log(n)) O(log(n)) O(n)
AVL Tree O(log(n)) O(log(n)) O(log(n)) O(log(n)) O(log(n)) O(log(n)) O(log(n)) O(log(n)) O(n)

数组排序算法

算法 时间复杂度 空间复杂度
  最佳 平均 最差 最差
Quicksort O(n log(n)) O(n log(n)) O(n^2) O(log(n))
Mergesort O(n log(n)) O(n log(n)) O(n log(n)) O(n)
Timsort O(n) O(n log(n)) O(n log(n)) O(n)
Heapsort O(n log(n)) O(n log(n)) O(n log(n)) O(1)
Bubble Sort O(n) O(n^2) O(n^2) O(1)
Insertion Sort O(n) O(n^2) O(n^2) O(1)
Selection Sort O(n^2) O(n^2) O(n^2) O(1)
Shell Sort O(n) O((nlog(n))^2) O((nlog(n))^2) O(1)
Bucket Sort O(n+k) O(n+k) O(n^2) O(n)
Radix Sort O(nk) O(nk) O(nk) O(n+k)

图操作

节点 / 边界管理 存储 增加顶点 增加边界 移除顶点 移除边界 查询
Adjacency list O(|V|+|E|) O(1) O(1) O(|V| + |E|) O(|E|) O(|V|)
Incidence list O(|V|+|E|) O(1) O(1) O(|E|) O(|E|) O(|E|)
Adjacency matrix O(|V|^2) O(|V|^2) O(1) O(|V|^2) O(1) O(1)
Incidence matrix O(|V| ⋅ |E|) O(|V| ⋅ |E|) O(|V| ⋅ |E|) O(|V| ⋅ |E|) O(|V| ⋅ |E|) O(|E|)

堆操作

类型 时间复杂度
  Heapify 查找最大值 分离最大值 提升键 插入 删除 合并
Linked List (sorted) - O(1) O(1) O(n) O(n) O(1) O(m+n)
Linked List (unsorted) - O(n) O(n) O(1) O(1) O(1) O(1)
Binary Heap O(n) O(1) O(log(n)) O(log(n)) O(log(n)) O(log(n)) O(m+n)
Binomial Heap - O(1) O(log(n)) O(log(n)) O(1) O(log(n)) O(log(n))
Fibonacci Heap - O(1) O(log(n)) O(1) O(1) O(log(n)) O(1)

大 O 复杂度图表

Big O Complexity Graph

Big O Complexity Graph

原文发布时间为:2016-06-20

本文来自云栖社区合作伙伴“Linux中国”

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

相关文章
常用算法和复杂度总结
一、常用算法和复杂度 算法 名称 复杂度 备注 快速排序 QuickSort(A,p,r) 最坏:O(n2) 平均:O(nlog n) 均衡划分:O(nlog n) ...
3105 0
数据结构面试之十二——排序3(排序算法归类、排序时间、空间复杂度、稳定性总结)
十一、数据结构面试之十二——排序3(排序算法归类、排序时间、空间复杂度、稳定性总结)
6 0
算法的时间复杂度(计算实例)
算法的时间复杂度定义:如果一个问题的规模是n,解这一问题的某一算法所需要的时间为T(n),它是n的某一函数 T(n)称为这一算法的“时间复杂性”。
537 0
冰与火之歌:「时间」与「空间」复杂度 | 算法必看系列三十六
对于一个算法,其时间复杂度和空间复杂度往往是相互影响的。当追求一个较好的时间复杂度时,可能会使空间复杂度的性能变差,即可能导致占用较多的存储空间; 反之,求一个较好的空间复杂度时,可能会使时间复杂度的性能变差,即可能导致占用较长的运行时间。另外,算法的所有性能之间都存在着或多或少的相互影响。因此,当设计一个算法(特别是大型算法)时,要综合考虑算法的各项性能,算法的使用频率,算法处理的数据量的大小,算法描述语言的特性,算法运行的机器系统环境等各方面因素,才能够设计出比较好的算法。
2200 0
阿里云服务器端口号设置
阿里云服务器初级使用者可能面临的问题之一. 使用tomcat或者其他服务器软件设置端口号后,比如 一些不是默认的, mysql的 3306, mssql的1433,有时候打不开网页, 原因是没有在ecs安全组去设置这个端口号. 解决: 点击ecs下网络和安全下的安全组 在弹出的安全组中,如果没有就新建安全组,然后点击配置规则 最后如上图点击添加...或快速创建.   have fun!  将编程看作是一门艺术,而不单单是个技术。
4444 0
程序员必知的10大基础实用性算法
转载自:http://www.apkbus.com/portal.php?mod=view&aid=9839     算法一:快速排序算法   快速排序是由东尼·霍尔所发展的一种排序算法。
881 0
好程序员web前端分享javascript枚举算法
好程序员web前端分享javascript枚举算法,题目:在1,2,3,4,5 五个数中,我们随机选取 3个数。问有多少种取法?并且把每种取出数的方法列举出来。 乍看这道题,其实感觉没什么难度。三个for循环不就解决问题了。
940 0
利用Clion对几种排序算法进行时间复杂度与空间复杂度的分析
算法 利用算法解决问题的步骤: 1、将问题模型化 2、找到一个合适的算法 3、这个算法足够快吗?对空间友好吗 4、如果不是,找出为什么 5、找到一个方法解决这个问题 6、一直迭代直到这个问题被解决 ...
979 0
+关注
10077
文章
2994
问答
文章排行榜
最热
最新
相关电子书
更多
文娱运维技术
立即下载
《SaaS模式云原生数据仓库应用场景实践》
立即下载
《看见新力量:二》电子书
立即下载