算法复杂度速查表

数据结构

数据结构

时间复杂度

空间复杂度

平均

最差

最差

访问

搜索

插入

删除

访问

搜索

插入

删除

数组

O(1)

O(n)

O(n)

O(n)

O(1)

O(n)

O(n)

O(n)

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)

双向链表

O(n)

O(n)

O(1)

O(1)

O(n)

O(n)

O(1)

O(1)

O(n)

跳跃列表

O(log(n))

O(log(n))

O(log(n))

O(log(n))

O(n)

O(n)

O(n)

O(n)

O(n log(n))

哈希表

O(1)

O(1)

O(1)

O(n)

O(n)

O(n)

O(n)

二叉搜索树

O(log(n))

O(log(n))

O(log(n))

O(log(n))

O(n)

O(n)

O(n)

O(n)

O(n)

笛卡尔树

O(log(n))

O(log(n))

O(log(n))

O(n)

O(n)

O(n)

O(n)

B树

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)

红黑树

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)

伸展树

O(log(n))

O(log(n))

O(log(n))

O(log(n))

O(log(n))

O(log(n))

O(n)

AVL树

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)

排序算法

算法

时间复杂度

空间复杂度

 

最佳

平均

最差

最差

快速排序

O(n log(n))

O(n log(n))

O(n^2)

O(log(n))

归并排序

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)

堆排序

O(n log(n))

O(n log(n))

O(n log(n))

O(1)

冒泡排序

O(n)

O(n^2)

O(n^2)

O(1)

插入排序

O(n)

O(n^2)

O(n^2)

O(1)

选择排序

O(n^2)

O(n^2)

O(n^2)

O(1)

希尔排序

O(n)

O((nlog(n))^2)

O((nlog(n))^2)

O(1)

桶排序

O(n+k)

O(n+k)

O(n^2)

O(n)

基数排序

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)

发表评论

电子邮件地址不会被公开。 必填项已用*标注