一:基础算法学习之基础具备条件
(1) : 在我看来,学习算法之前应先了解数据结构和C++STL中的一些基础知识
二:先了解C++STL中的基础知识
在我初步学习算法和数据结构时,我发现C++中的STL中容器操作和理解对此学习帮助很大,那么就需要对这些容器具有基本的了解。
1. 序列式容器
容器 |
特性 |
时间复杂度 |
vector |
动态数组,支持随机访问 |
插入/删除末尾:O(1),中间:O(n) |
deque |
双端队列,头尾插入高效 |
头尾插入/删除:O(1) |
list |
双向链表,任意位置插入高效 |
插入/删除:O(1),访问:O(n) |
forward_list |
单向链表,节省内存 |
插入/删除:O(1),访问:O(n) |
array |
固定大小数组(C++11) |
访问:O(1) |
2. 关联式容器
容器 |
特性 |
时间复杂度 |
set |
唯一键集合,基于红黑树 |
插入/查找:O(log n) |
multiset |
允许重复键的集合 |
同上 |
map |
键值对集合,键唯一 |
同上 |
multimap |
允许重复键的键值对 |
同上 |
unordered_set |
哈希表实现的集合(C++11) |
平均O(1),最差O(n) |
unordered_map |
哈希表实现的键值对(C++11) |
同上 |
3. 容器适配器
容器 |
底层容器 |
特性 |
stack |
deque /list |
LIFO(后进先出) |
queue |
deque /list |
FIFO(先进先出) |
priority_queue |
vector |
元素按优先级排序(默认大顶堆)
|
4.容器中的常用算法
分类 |
示例算法 |
功能 |
非修改序列算法 |
find , count , for_each |
遍历或统计 |
修改序列算法 |
copy , fill , replace |
修改元素值 |
排序算法 |
sort , stable_sort , partial_sort |
排序或部分排序 |
数值算法 |
accumulate , inner_product |
数学运算(求和、内积等) |
接下来就是数据结构的基础知识:
三:数据结构的简单分类
1.线性结构
数据元素按线性顺序排列,每个元素最多有一个前驱和一个后继。
数据结构 |
特点 |
典型应用场景 |
数组 |
连续内存,固定大小,支持随机访问 |
高频访问、低增删场景(如图像处理) |
链表 |
非连续内存,动态大小,插入/删除高效 |
内存池、LRU缓存 |
栈 |
后进先出(LIFO),仅允许一端操作 |
函数调用栈、表达式求值 |
队列 |
先进先出(FIFO),允许两端操作 |
消息队列、BFS算法 |
双端队列 |
两端均可插入/删除 |
滑动窗口算法 |
2.树形结构
数据元素存在层次关系,每个元素可能有多个后继。
数据结构 |
特点 |
典型应用场景 |
二叉树 |
每个节点最多两个子节点 |
表达式树、哈夫曼编码 |
二叉搜索树 |
左子树值 < 根 < 右子树值 |
动态数据排序(如数据库索引) |
AVL树 |
自平衡二叉搜索树,高度差≤1 |
需要严格平衡的场景 |
红黑树 |
近似平衡的二叉搜索树,插入/删除效率更高 |
C++ map /set 底层实现 |
堆 |
完全二叉树,根节点极值(大顶堆/小顶堆) |
优先级队列、Top K问题 |
Trie树 |
前缀树,用于字符串快速检索 |
输入法词库、IP路由表 |
3.散列结构
通过哈希函数直接定位数据,理想情况下访问时间为O(1)。
数据结构 |
特点 |
典型应用场景 |
哈希表 |
键值对存储,冲突解决(开放寻址/链地址法) |
快速查找(如Redis字典) |
布隆过滤器 |
空间效率极高的概率型数据结构,可能误判 |
垃圾邮件过滤、缓存穿透防护 |
4.图结构
数据元素多对多关系,由顶点和边组成。
数据结构 |
特点 |
典型应用场景 |
邻接矩阵 |
二维数组表示边,适合稠密图 |
Floyd最短路径算法 |
邻接表 |
链表存储边,适合稀疏图 |
社交网络关系图 |
十字链表 |
优化有向图的邻接表 |
编译器依赖分析 |
逆邻接表 |
快速获取入边信息 |
网页爬虫链接分析 |
6.其他特殊结构
数据结构 |
特点 |
典型应用场景 |
并查集 |
高效合并/查询集合 |
朋友圈关系、Kruskal算法 |
跳表 |
多层链表加速搜索,媲美平衡树 |
Redis有序集合 |
位图 |
用bit位标记数据,极致压缩空间 |
海量数据去重 |
7.选择原则
- 访问频率高 → 数组/哈希表
- 频繁增删 → 链表/跳表
- 需要排序 → 平衡搜索树
- 层级关系 → 树形结构
- 网络关系 → 图结构
掌握这些基础分类后,可进一步学习其变体(如B树、LSM树等)及具体实现细节。
说到算法,必定离不开算法时间复杂度和空间复杂度分析,这两个代表着你的算法是否是高效的,优化的。
四:常见的一些算法时间复杂度分析
1.排序算法
算法 |
最优时间 |
平均时间 |
最差时间 |
空间复杂度 |
稳定性 |
特点 |
冒泡排序 |
O(n) |
O(n²) |
O(n²) |
O(1) |
稳定 |
简单但效率低 |
选择排序 |
O(n²) |
O(n²) |
O(n²) |
O(1) |
不稳定 |
交换次数最少 |
插入排序 |
O(n) |
O(n²) |
O(n²) |
O(1) |
稳定 |
对小规模数据高效 |
快速排序 |
O(n log n) |
O(n log n) |
O(n²) |
O(log 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) |
不稳定 |
适合Top K问题 |
计数排序 |
O(n + k) |
O(n + k) |
O(n + k) |
O(n + k) |
稳定 |
非比较排序,k为数值范围 |
基数排序 |
O(nk) |
O(nk) |
O(nk) |
O(n + k) |
稳定 |
按位排序,k为位数 |
2.搜索算法
算法 |
时间复杂度 |
空间复杂度 |
适用场景 |
线性搜索 |
O(n) |
O(1) |
无序数据 |
二分查找 |
O(log n) |
O(1) |
有序数组(需随机访问) |
哈希表查找 |
O(1) |
O(n) |
键值对快速访问 |
BFS/DFS |
O(V + E) |
O(V) |
图/树的遍历(V:顶点,E:边) |
A* |
O(b^d) |
O(b^d) |
启发式路径搜索(b:分支因子) |
3.图算法
算法 |
时间复杂度 |
空间复杂度 |
特点 |
Dijkstra |
O(V²) |
O(V) |
无负权边的最短路径(朴素实现) |
Dijkstra+堆 |
O(E log V) |
O(V) |
稀疏图优化版 |
Bellman-Ford |
O(VE) |
O(V) |
支持负权边检测负环 |
Floyd-Warshall |
O(V³) |
O(V²) |
多源最短路径 |
Prim |
O(V²) |
O(V) |
最小生成树(稠密图) |
Kruskal |
O(E log V) |
O(E) |
最小生成树(稀疏图) |
4.动态规划
问题类型 |
时间复杂度 |
空间复杂度 |
经典问题 |
斐波那契数列 |
O(n) |
O(1) |
基础递推问题 |
背包问题 |
O(nW) |
O(W) |
W为背包容量 |
LCS |
O(mn) |
O(mn) |
最长公共子序列(m,n为字符串长度) |
矩阵链乘法 |
O(n³) |
O(n²) |
最优括号化方案 |
5.字符串匹配
算法 |
预处理时间 |
匹配时间 |
空间复杂度 |
特点 |
暴力匹配 |
- |
O(mn) |
O(1) |
简单但效率低 |
KMP |
O(m) |
O(n) |
O(m) |
利用部分匹配表跳过比较 |
Boyer-Moore |
O(m + k) |
O(n/m) |
O(k) |
坏字符规则加速(k为字符集大小) |
Rabin-Karp |
O(m) |
O(n + m) |
O(1) |
哈希滚动匹配 |
6.数据结构操作
数据结构 |
插入/删除 |
查找 |
访问 |
备注 |
数组 |
O(n) |
O(n) |
O(1) |
插入/删除需移动元素 |
链表 |
O(1) |
O(n) |
O(n) |
随机访问效率低 |
哈希表 |
O(1) |
O(1) |
O(1) |
冲突时可能退化到O(n) |
平衡二叉搜索树 |
O(log n) |
O(log n) |
O(log n) |
如AVL树、红黑树 |
堆 |
O(log n) |
- |
O(1) |
仅能快速访问堆顶 |
7.递归算法
算法类型 |
时间复杂度 |
空间复杂度 |
示例 |
汉诺塔 |
O(2ⁿ) |
O(n) |
经典递归问题 |
分治算法 |
O(n log n) |
O(log n) |
归并排序、快速排序 |
回溯算法 |
O(bᵈ) |
O(d) |
八皇后问题(b:分支,d:深度) |
8.关键总结
-
时间与空间的权衡:
- 快速排序(时间优) vs 归并排序(空间优)
- 哈希表(时间O(1)) vs 平衡树(空间更紧凑)
-
算法选择原则:
- 小数据(n ≤ 100):插入排序
- 大数据且需稳定:归并排序
- 图搜索:稀疏图用堆优化Dijkstra,稠密图用Floyd
-
最坏情况预防:
- 快速排序可通过随机化枢轴避免O(n²)
- 哈希表可通过扩容减少冲突
掌握这些复杂度规律,能帮助你在实际开发中高效选择算法!
五:个人总结
上边的知识点在我看来比较全面,但是自己并不掌握的很好,我也发现,在后边的学习中,这些最基础的,往往是最重要的。所以,在学习的过程中,不能好高骛远,必须脚踏实地,打牢基础,及时复习巩固,希望自己在日后的学习中能够很好的认识每一次自己的不足和快速查漏补缺!
饲料网