每个程序员都应该收藏的算法复杂度速查表-软件开发|Linux.中国-开源社区

https://linux.cn/article-7480-1.html

算法复杂性速查表

图例

绝佳

不错

一般

不佳

糟糕

数据结构操作

数据结构	时间复杂度								空间复杂度
	平均				最差				最差
	访问	搜索	插入	删除	访问	搜索	插入	删除
	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)
	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)
	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)
	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)

图操作

节点 / 边界管理	存储	增加顶点	增加边界	移除顶点	移除边界	查询
	O(|V|+|E|)	O(1)	O(1)	O(|V| + |E|)	O(|E|)	O(|V|)
	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)
	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)
	O(n)	O(1)	O(log(n))	O(log(n))	O(log(n))	O(log(n))	O(m+n)
	-	O(1)	O(log(n))	O(log(n))	O(1)	O(log(n))	O(log(n))
	-	O(1)	O(log(n))	O(1)	O(1)	O(log(n))	O(1)