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

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)

O(n)

O(n)

O(1)

O(1)

O(n)

O(n)

O(1)

O(1)

O(n)

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)

O(nk)

O(nk)

O(nk)

O(n+k)

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|)

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

-

O(1)

O(1)

O(n)

O(n)

O(1)

O(m+n)

-

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 复杂度图表

0 条评论

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

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

• ### 探究官方 JSON 与阿里的 FastJSON 中 put 方法

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

• ### Java编程常见问题汇总2

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

• ### shell脚本快速入门之-----函数

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

• ### 生产环境日志清理脚本

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

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

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

• ### 机器学习 - 交叉熵Cross Entropy

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

• ### 储备点数学公式

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

• ### 简单的交叉熵损失函数，你真的懂了吗？

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