搜索
算法
数据结构
时间复杂度
空间复杂度
平均
最差
最差
| 深度优先搜索 (DFS) |
Graph of |V| vertices and |E| edges |
- |
O(|E| + |V|) |
O(|V|) |
| 广度优先搜索 (BFS) |
Graph of |V| vertices and |E| edges |
- |
O(|E| + |V|) |
O(|V|) |
| 二分查找 |
Sorted array of n elements |
O(log(n)) |
O(log(n)) |
O(1) |
|
穷举查找 |
Array |
O(n) |
O(n) |
O(1) |
| 最短路径-Dijkstra，用小根堆作为优先队列 |
Graph with |V| vertices and |E| edges |
O((|V| + |E|) log |V|) |
O((|V| + |E|) log |V|) |
O(|V|) |
| 最短路径-Dijkstra，用无序数组作为优先队列 |
Graph with |V| vertices and |E| edges |
O(|V|^2) |
O(|V|^2) |
O(|V|) |
| 最短路径-Bellman-Ford |
Graph with |V| vertices and |E| edges |
O(|V||E|) |
O(|V||E|) |
O(|V|) |
排序
算法
数据结构
时间复杂度
最坏情况下的辅助空间复杂度
最佳
平均
最差
最差
| 快速排序 |
数组 |
O(n log(n)) |
O(n log(n)) |
O(n^2) |
O(n) |
| 归并排序 |
数组 |
O(n log(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+k) |
O(n+k) |
O(n^2) |
O(nk) |
| 基数排序 |
数组 |
O(nk) |
O(nk) |
O(nk) |
O(n+k) |
数据结构
数据结构
时间复杂度
空间复杂度
平均
最差
最差
索引
查找
插入
删除
索引
查找
插入
删除
| 基本数组 |
O(1) |
O(n) |
- |
- |
O(1) |
O(n) |
- |
- |
O(n) |
| 动态数组 |
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(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) |
堆
Heaps
时间复杂度
建堆
查找最大值
提取最大值
Increase Key
插入
删除
合并
| 链表（已排序） |
- |
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(log(n)) |
O(log(n)) |
O(log(n)) |
O(log(n)) |
O(log(n)) |
O(log(n)) |
| 斐波那契堆 |
- |
O(1) |
O(log(n))* |
O(1)* |
O(1) |
O(log(n))* |
O(1) |
图
节点 / 边 管理
Storage
Add Vertex
Add Edge
Remove Vertex
Remove Edge
Query
| 邻接表 |
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|) |
英文版链接：http://bigocheatsheet.com/
分享到：
相关推荐
速查表：常用算法和时间复杂度，算法数据结构 五大常用算法
数据结构与算法复杂度速查表是一款对常用数据结构与算法的复杂程度进行快速查询的表格。 数据结构与算法复杂度速查表演示图：
2.3.1 时间复杂度的组成 2.3.2 操作计数 2.3.3 最好、最坏和平均操作计数 2.3.4 步数 第3章 渐近记法 3.1 引言 3.2 渐近记法 3.2.1 大Ο记法 3.2.2 渐近记法Ω和Θ 3.3 渐近数学（可选） 3.3.1 大O记法 3.3.2 Ω记法...
主要内容包括SQL的基础理论、查询优化、查询算法及复杂度，以及在使用子查询、表表达式、排名函数、数据聚合和透视转换、TOP和APPLY、数据修改、分区表、特殊数据结构等实际应用时会遇到的各种高级查询问题和解决...
7若长度为n的线性表采用顺序存储结构，在其第个i位置插入一个新元素算法的时间复杂度为（ ）。A、 O(log2n)B、O(1)C、O(n)D、O(n2) 正确答案： C 8线性表的静态链表存储结构与顺序存储结构相比优点是（ ）。A、...
主要内容包括SQL的基础理论、查询优化、查询算法及复杂度，以及在使用子查询、表表达式、排名函数、数据聚合和透视转换、TOP和APPLY、数据修改、分区表、特殊数据结构等实际应用时会遇到的各种高级查询问题和解决...
主要内容包括SQL的基础理论、查询优化、查询算法及复杂度，以及在使用子查询、表表达式、排名函数、数据聚合和透视转换、TOP和APPLY、数据修改、分区表、特殊数据结构等实际应用时会遇到的各种高级查询问题和解决...
(55) 在设计程序时，应采纳的原则之一是(A) 注：和设计风格有关 A. 程序结构应有助于读者理解 B. 不限制goto语句的使用 C. 减少或取消注解行 D. 程序越短越好 (56) 下列不属于软件调试技术的是(B) 注：P98 A. 强行...
实验结果表明该方法不仅可以很好地删除噪声数据和冗余信息，尤其是类区域内样本，减小数据的不平衡度和样本总量，而且由于算法时间复杂度是线性阶的，在样本数量很大的情况下，运行速度非常快，适合从海量的数据中...
这道题结果输出所有问询距离总数，可采用了Tarjan离线算法（一次读入所有查询，统一处理），基于DFS和并查集（这两个知识点西安讲师在视频中讲过）， （根节点可以任选）在该过程中，维护一个所有节点到选定根的距离...
答：空间复杂度和时间复杂度 (27) 数据结构包括数据的逻辑结构、数据的 ______以及对数据的*作运算。 答：存储结构 (28) 一个类可以从直接或间接的祖先中继承所有属性和方法。采用这个方法提高了软件的______。 答...
算法复杂度 搜索和排序算法 参考： 第 6-10 章。 随机规划 随机性 创建模拟 蒙特卡罗模拟 绘图 NumPy 简单统计 基本统计查询 参考： 第 11-14 章。 第 4 周 常用表达 使用 Pandas 加载和操作数据 常用数据格式 ...
龙 翀 -《解决空间规模问题的几种常用的存储结构》 骆 骥 -《数学模型的建立和选择》 施 遥 -《人工智能在围棋程序中的应用》 肖 洲 -《数据结构的在程序设计中的应用》 谢 婧 -《规模化问题的解题策略》 徐 串...
算法的基本运算和操作包括：算术运算、逻辑运算、关系运算、数据传输。 （3）算法的3种基本控制结构 算法的3种基本控制结构是：顺序结构、选择结构、循环结构。 （4）算法基本设计方法 算法基本设计方法：列举法、...
学习研磨设计模式，记录项目的速查目录，方便查询对应模式的具体实现方式。 四、数据库 五、操作系统 基础核心概念、常用命令使用 六、网络 HTTP请求响应、持久连接、会话跟踪、跨站攻击 HTTPS工作过程、TLS证书...
答：对于复杂而开发时间紧的项目时，可以采用C语言，但前提是要求对该MCU系统的C语言和C编译器非常熟悉，特别要注意该C编译系统所能支持的数据类型和算法。虽然C语言是最普遍的一种高级语言，但不同的MCU厂家其...
需求模型的表现形式有自然语言、半形式化(如图、表、结构化英语等)和形式化表示等三种。需求概念模型的要求包括实现的独立性:不模拟数据的表示和内部组织等；需求模拟技术又分为企业模拟、功能需求模拟和非功能需求...
数据库集群和库表散列 150 缓存 151 镜像 151 负载均衡 152 【网络】说说你对Http协议和Socket协议的理解 153 http协议 153 Tcp协议 154 【网络】HTTPS的工作原理说明HTTPS是安全的 155 【消息队列】为什么要使用...
详细设计需要从实现每个模块功能的程序算法和模块内部的局部数据结构等细节内容上给出设计说明，并以“详细设计说明书”的形式提交书面报告。 3．编码和单元测试 编码是对软件的实现，一般由程序员完成，并以获得源...
重表的方式加以优化，以降低其时间和空间复杂度。 2. 总体架构 本项目总体架构如下图所示： 配置器 Configurator 超文本传输协议响应 HttpResponse 日志 Log 主线程 main 多路输入输出 MultiIo 插件管理器 ...