每个程序员都应该收藏的算法复杂度速查表 – 码农网1
需积分: 0 99 浏览量
2022-08-04
11:37:03
上传
评论
收藏 571KB PDF 举报
首页 Java JavaScript PHP iOS Android HTML5 CSS3 Linux C++ Python C# Node.Js
分享到：
更多 4
每个程序员都应该收藏的算法复杂度速查表
2016-06-22分类：算法设计、编程开发、首页精华 暂无人评论来源：linux.cn
算法复杂度这件事
这篇文章覆盖了计算机科学里面常见算法的时间和空间的大O（Big-O）复杂度。我之前在参加面试
前，经常需要花费很多时间从互联网上查找各种搜索和排序算法的优劣，以便我在面试时不会被问住。
最近这几年，我面试了几家硅谷的初创企业和一些更大一些的公司，如Yahoo、eBay、LinkedIn和Go
ogle，每次我都需要准备这个，我就在问自己，“为什么没有人创建一个漂亮的大O速查表呢？”所
以，为了节省大家的时间，我就创建了这个，希望你喜欢！
—Eric
图例
绝佳 不错 一般 不佳 糟糕
数据结构操作
数据结构 时间复杂度
平均 最差
访问 搜索 插入 删除 访问 搜索 插入 删除
Array O(1) O(n) O(n) O(n) O(1) O(n) O(n) O(n)
Stack O(n) O(n) O(1) O(1) O(n) O(n) O(1) O(1)
Singly-LinkedList O(n) O(n) O(1) O(1) O(n) O(n) O(1) O(1)
Doubly-LinkedLis
t
O(n) O(n) O(1) O(1) O(n) O(n) O(1) O(1)
SkipList O(log(n)) O(log(n)) O(log(n)) O(log(n)) O(n) O(n) O(n) O(n)
HashTable - O(1) O(1) O(1) - O(n) O(n) O(n)
BinarySearchTree O(log(n)) O(log(n)) O(log(n)) O(log(n)) O(n) O(n) O(n) O(n)
CartesianTree - O(log(n)) O(log(n)) O(log(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))
Red-BlackTree O(log(n)) O(log(n)) O(log(n)) O(log(n)) O(log(n)) O(log(n)) O(log(n)) O(log(n))
SplayTree - O(log(n)) O(log(n)) O(log(n)) - O(log(n)) O(log(n)) O(log(n))
AVLTree O(log(n)) O(log(n)) O(log(n)) O(log(n)) O(log(n)) O(log(n)) O(log(n)) O(log(n))
数组排序算法
算法 时间复杂度
最佳 平均 最差
Quicksort O(nlog(n)) O(nlog(n)) O(n^2)
Mergesort O(nlog(n)) O(nlog(n)) O(nlog(n))
Timsort O(n) O(nlog(n)) O(nlog(n))
Heapsort O(nlog(n)) O(nlog(n)) O(nlog(n))
BubbleSort O(n) O(n^2) O(n^2)
InsertionSort O(n) O(n^2) O(n^2)
SelectionSort O(n^2) O(n^2) O(n^2)
ShellSort O(n) O((nlog(n))^2) O((nlog(n))^2)
BucketSort O(n+k) O(n+k) O(n^2)
RadixSort O(nk) O(nk) O(nk)
图操作
节点/边界管理 存储 增加顶点 增加边界 移除顶点 移除边界
Adjacencylist O(|V|+|E|) O(1) O(1) O(|V|+|E|) O(|E|)
Incidencelist O(|V|+|E|) O(1) O(1) O(|E|) O(|E|)
Adjacencymatrix O(|V|^2) O(|V|^2) O(1) O(|V|^2) O(1)
Incidencematrix O(|V|⋅|E|) O(|V|⋅|E|) O(|V|⋅|E|) O(|V|⋅|E|) O(|V|⋅|E|)
堆操作
类型 时间复杂度
Heapify 查找最大值 分离最大值 提升键 插入 删除
我在编程中遇到了一个问题？
我要提问
编程不需要天赋和激情
C#Lambda表达式的前世今生
22个AndroidStudio优秀插件汇总
AngularJS样式指南介绍
Java远程通讯技术及原理分析
游戏编程十年总结
程序员眼中的古典名画
记一次Google面试经历
80多个Linux系统管理员的监控工具
对优秀程序员的思考
编程不需要天赋和激情
入门软件工程师所面临的5个挑战
程序员编程的7+1条小贴士
假如程序员生活在童话里…
一个32岁入门的70后程序员给我的启示
程序员每天都在使用的6个惊讶的软技能
一流程序员完全可以有编程之外的生活
回顾15年程序员生涯，我总结的7点经验
为什么开源可以提高程序员的编程技能？
程序员的走与留？
JavaScript实现简单的神经网络算法
程序员编程的7+1条小贴士
假如程序员生活在童话里…
一个32岁入门的70后程序员给我的启示
程序员每天都在使用的6个惊讶的软技能
热门文章
职场人生
相关文章
Java
RSS 微博
程序员
RSS 微博
Android
RSS
PHP
RSS
JavaScript
RSS
Linux
RSS
关注我们的微博
程序员俱乐
部
加关注
付费投稿计划
点击查看详情
热门栏目订阅
首页 问答 热门文章
评论0