专栏首页java一日一条每个程序员都应该收藏的算法复杂度速查表

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

算法复杂度这件事

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

本文分享自微信公众号 - java一日一条(mjx_java),作者:收听我

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2016-07-18

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • Java中的clone() 深拷贝 浅拷贝

    上图展示了浅拷贝:对于非基本数据类型,clone过后,结果两个指针指向了同一块儿内存空间,所以仅仅是浅拷贝,这样的话如果对一个对象进行操作,另一个内容也会变,这...

    哲洛不闹
  • 探究官方 JSON 与阿里的 FastJSON 中 put 方法

    首先json.org给出的jar包能够正常运行出你想要的结果,但是fastjson就会给你一些惊喜(自己试一下吧)。

    哲洛不闹
  • Java编程常见问题汇总2

    这里有一个前提,就是文件大小不能讲JVM的heap撑爆。否则就等着OOM吧,尤其是在高并发的服务器端代码。最好的做法是采用Stream的方式边读取边存储(本地文...

    哲洛不闹
  • shell脚本快速入门之-----函数

    函数可以让我们将一个复杂功能划分成若干模块,让程序结构更加清晰,代码重复利用率更高。像其他编程语言一样,shell也支持函数。shell函数必须先定义后使用

    不吃小白菜
  • 生产环境日志清理脚本

    生产上有40多个微服务部署的应用,每个应用都会产生日志,随着时间的增长,日志量不断增大,现需要清理。有两个重要的应用日志需保留90天,其它应用保留20天。

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

    算法复杂度这件事 这篇文章覆盖了计算机科学里面常见算法的时间和空间的大 O(Big-O)复杂度。我之前在参加面试前,经常需要花费很多时间从互联网上查找各种搜索和...

    用户1667431
  • 机器学习 - 交叉熵Cross Entropy

    [1] - Caffe Loss 层 - SigmoidCrossEntropyLoss 推导与Python实现

    AIHGF
  • 储备点数学公式

    近日淘到一本不可多得的好书,开篇便是扎实数学功底。所以本篇就来推导一些算法抉择必备的数学功底,不然哪套算法好,好在哪里,也说不出个所以然来,空口无凭,公式说话!

    看、未来
  • 简单的交叉熵损失函数,你真的懂了吗?

    版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.n...

    红色石头
  • 记录日志

    华创信息技术

扫码关注云+社区

领取腾讯云代金券