搜索
算法
数据结构
时间复杂度
空间复杂度
平均
最差
最差
| 深度优先搜索 (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/
分享到：
相关推荐
6. **图**：图的存储和操作（添加顶点、边，移除顶点、边，查询）的时间复杂度根据图的表示（邻接矩阵或邻接表）和具体操作而变化，范围从O(1)到O(|V|^2)。 了解这些基础的算法和数据结构的时间复杂度对于编写高效...
### 由数据范围反推算法复杂度及其应用 在计算机科学与编程竞赛中，了解算法的时间复杂度对于选择合适的算法解决特定问题至关重要。通过题目给出的数据规模（即输入数据的大小），我们可以反向推导出适合该问题的...
在编程领域，C语言因其高效、灵活和接近底层的特性，常常被用来实现各种算法。"C常用算法程序集"是一份宝贵的...通过研究和实践"C常用算法程序集"中的代码，程序员可以提升自己的编程技巧，更好地应对各种复杂问题。
### ACM竞赛常用算法和数据结构概览 #### 一、ACM竞赛背景及意义 ACM（Association for Computing Machinery）是计算机科学领域历史悠久且最具权威性的国际性组织，旨在推动信息技术专业人员和学生的技能提升。它...
本压缩包文件“C常用算法程序集”显然是一份包含了多种常见算法的代码集合，旨在帮助程序员理解和实践这些算法。 首先，我们来探讨一些基础的C语言算法。C语言中的基本算法包括排序算法、查找算法、递归算法、字符...
《C语言算法速查手册源代码（含目录）》是一份非常实用的资源，它包含了C语言编程中常用的算法实现和详细的速查信息。这份资料的重要性在于，它为程序员提供了快速理解和应用各种算法的途径，无论是初学者还是经验...
10. 树状数组/C++的STL中的 Fenwick Tree：用于在线性时间复杂度内进行区间查询和更新操作。 通过深入学习这些算法和数据结构，不仅能在ACM竞赛中取得优势，还能提升编程思维，为软件开发、数据分析等领域打下坚实...
《C语言算法速查手册》是一本非常实用的编程指南，专为那些希望深入理解和熟练运用C语言进行算法实现的读者而设计。这本书涵盖了从基础到高级的各种算法，旨在帮助程序员快速查找并理解如何在C语言中实现这些算法。...
"c_c++语言常用算法源代码"这个资源包含了大量经典算法的实现，对于学习和理解算法有着极大的帮助。 1. **排序算法**：包括快速排序、归并排序、插入排序、选择排序、冒泡排序等。排序是计算机科学中最基础的算法之...
5. **空间复杂度和时间复杂度**：LFU算法的空间复杂度主要取决于哈希表和优先队列的大小，而时间复杂度主要由元素访问、淘汰和频率升级操作决定。在实际应用中，为了优化性能，可以采用近似的LFU算法，例如固定频率...
2. 分治法：分治法是一种常用的算法优化策略，它将问题分解成若干小问题，每个小问题都可以独立解决，然后将这些小问题的解组合起来形成最终的解。例如，在最大子段和问题中，分治法可以将序列分成两个相等的部分，...
"C常用算法程序"这个压缩包文件显然包含了各种常见的算法实现，这些算法是计算机科学和软件开发的基础，对于学习和提升C语言编程技能至关重要。下面，我们将详细探讨这些常见算法及其在C语言中的应用。 1. 排序算法...
该算法的时间复杂度平均为O(n log n)，在实际应用中非常常用。 一、快速排序算法的基本思想 快速排序的基本思想是通过选择一个pivot元素，将数组分成两个部分：左侧元素都小于pivot，右侧元素都大于pivot。然后...
10. **算法效率**：在处理大量数据时，理解算法的时间复杂度和空间复杂度至关重要，这决定了算法在实际应用中的性能。 这个压缩包“01 常用集合算法”很可能包含了这些概念的详细解释、实例代码和练习，对于C++初学...
- 通过预计算和缓存常用聚合结果，可以进一步提高查询速度。 6. **限制返回的数据量(Limiting Data Returned)**： - 在不需要所有数据的情况下，使用LIMIT关键字来限制查询结果的数量，减少网络传输负担。 7. **...
- **快速排序**：快速且常用，平均时间复杂度为O(nlogn)，最坏情况O(n^2)。Java的`Arrays.sort()`在不同情况下会使用双轴快速排序。 - **插入排序**：简单排序，适合小规模或部分有序数据，最好情况O(n)。 - **...
在ACM（国际大学生程序设计竞赛）中，掌握常用算法是至关重要的。这些算法不仅能够帮助参赛者在有限的时间内解决复杂问题，还能培养出高效编程的思维模式。本资料集合了数据结构、程序设计竞赛及经典算法的相关知识...
"C语言常用算法源代码"这个资源集合，是学习和研究C语言算法实现的重要参考资料。下面我们将深入探讨这个主题，详细解析其中可能包含的一些常见算法及其应用。 1. **排序算法**： - **冒泡排序**：通过不断交换...