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

算法复杂度这件事

这篇文章覆盖了计算机科学里面常见算法的时间和空间的大 O(Big-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 复杂度图表

原文发布于微信公众号 - 大数据钻研(bigdata118)

原文发表时间:2016-06-24

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏菩提树下的杨过

scala 学习笔记(03) 参数缺省值、不定个数参数、类的属性(Property)、泛型初步

继续学习,这一篇主要是通过scala来吐槽java的,同样是jvm上的语言,差距咋就这么大呢? 作为一个有.NET开发经验的程序员,当初刚接触java时,相信很...

3016
来自专栏Python数据科学

使用Pandas&NumPy进行数据清洗的6大常用方法

数据科学家花了大量的时间清洗数据集,并将这些数据转换为他们可以处理的格式。事实上,很多数据科学家声称开始获取和清洗数据的工作量要占整个工作的80%。

2692
来自专栏张善友的专栏

.NET不可变集合已经正式发布

微软基础类库(Base Class Library)团队已经完成了.NET不可变集合的正式版本,但不包括ImmutableArray。与其一起发布的还包括针对其...

23510
来自专栏阿凯的Excel

文本数字拆分技巧

Excel处理人员呢,最喜欢的就是规范化的表,那什么样子的表是规范的呢?给大家个图片感受一下! ? 今天的要和大家分享的就是和规范化图表格格不入的,需要由不规...

3466
来自专栏技术栈大杂烩

Python: 浅谈函数局部变量"快"在哪

意图很简单,就是将 somelib.get_all_projects 获取的项目塞入的 self.project_code_to_name

1373
来自专栏web前端教室

javascript 红皮高程(11)

为革命,重学JS高程,预备...齐! 3.4.7 object哈,对象。找不着对象的同学们,建议看看JS高程,就能找着对象了。 ECMAScript中的对象,是...

2075
来自专栏小詹同学

Leetcode打卡 | No.012 整数转罗马数字

欢迎和小詹一起定期刷leetcode,每周一和周五更新一题,每一题都吃透,欢迎一题多解,寻找最优解!这个记录帖哪怕只有一个读者,小詹也会坚持刷下去的!

1211
来自专栏飞雪无情的博客

Golang必备技巧:接口型函数

接口型函数,指的是用函数实现接口,这样在调用的时候就会非常简便,我称这种函数,为接口型函数,这种方式使用于只有一个函数的接口。

772
来自专栏工科狗和生物喵

【我的漫漫跨考路】数据结构·队列的链表实现

? 正文之前 今天看无穷级数这个数学内容实在看得头疼,索性看到八点多就不看了。愉快的写起了码,对我来说这个可有趣了!虽然有时候莫名其妙的就会Run succe...

2895
来自专栏小樱的经验随笔

基数排序与桶排序,计数排序【详解】

桶排序简单入门篇^-^ 在我们生活的这个世界中到处都是被排序过的东东。站队的时候会按照身高排序,考试的名次需要按照分数排序,网上购物的时候会按照价格排序,电子邮...

3747

扫码关注云+社区

领取腾讯云代金券