常见算法及其时间复杂度总结
提示：文章写完后，目录可以自动生成，如何生成可参考右边的帮助文档
前言
记录一些常见算法时间复杂度
O(1) < O(logn) < O(n) < O(nlogn) < O(n2 ) < O(n3) < O(2n) < O(n!) < O(nn)
一、O(1)
常见算法：数组随机存取、固定大小的循环、获取链表的长度或头尾节点、简单算术运算或位运算（+、-、*、/、&、|、~、^）、哈希散列表查找（unordered_map、unordered_set）
数组随机存取：数组具有
二、O(logn)
表示log2n
常见算法：for或while以i*2或i/2进行变化、二分查找、平衡二叉树查找（map、set）、分治算法
三、O(n)
常见算法：线性查找、以变量为迭代指标遍历、求和、计数、拷贝、阶乘算法、链表合并（max(m,n)）、计数排序、桶排序、广度优先搜索算法、深度优先搜索算法
四、O(nlogn)
常见算法：堆排序、快速排序、归并排序、希尔排序、计数排序、基数排序、C+±std::sort()
堆排序：大根堆、小根堆，属于二叉排序树/二叉搜索树/二叉查找树
快速排序：自上而下将数据进行分治
归并排序：自下而上将数据分治为小粒度，再进行合并
C++标准库的std::sort()：通常是使用快速排序、归并排序或堆排序等。
五、O(n^2)
常见算法：两层循环嵌套、冒泡排序、选择排序、插入排序、希尔排序、矩阵乘法朴素算法、求解线性方程组的高斯消元法
冒泡排序：两层循环，外层i正常遍历0 ~ n-1，内层j从0 ~ n-1-i，内层每一轮使j+1处数据>j处数据（如不满足则交换两位置数据）
选择排序：两层循环，外层i正常遍历0 ~ n-1，内层j从i+1 ~ n，内层每轮确定一个最小的数的位置，将之与i处的数据交换
插入排序：两层循环，外层i正常遍历1 ~ n-1，内层j从 i起往前遍历，确保j-1处的数据<j处的数据（如不满足则交换两位置数据）
六、O(n^3)
常见算法：三层循环嵌套、常规矩阵乘法、Floyd-Warshall 算法、求解线性方程组的高斯消元法
七、O(2^n)
常见算法：斐波那契递归、递归组合生成算法、动态规划的指数级实现
八、O(n!)
常见算法：全排列生成算法、旅行商问题暴力破解算法、递归字典序生成算法
九、O(nn)
常见算法：暴力搜索算法、递归全排列算法、递归子集生成算法、递归布尔表达式求解算法
总结
附上别处的总结图片对比参考：
稳定的排序算法：冒泡排序、插入排序、归并排序、基数排序
不稳定的排序算法：选择排序、快速排序、希尔排序、堆排序
各排序算法优化：
快速排序：
- 快排若默认选取第一个/最后一个作为标定点则时间复杂度在基本有序的原始数据上接近O(n2)，此时可以选用随机标定点，时间复杂度为O(nlogn)
- 对数据量低于20的递归部分采用插入排序
归并排序：
- 对数据量低于20的递归部分采用插入排序
冒泡排序 ：
- 使用标志位判断排序终点
插入排序：
- 向前查找时使用二分查找提高效率