关于算法时间复杂度的例子

O(1)

1. 数组中取出[i]位置元素，哈希表取出元素。通常哈希表比数组寻址慢很多。

2. 计算+-*/运算以及位运算。位运算一般最快。

3. 乘方慢很多，但也可以当成O1

4. 集合中查找元素是否存在，插入元素，删除元素。

5. 链表删除元素、双向链表删除节点

6. 通过数学公式求得一个结果，前n项和公式，xxxx通项公式。

O(logn)

1. 二分查找

2. 二叉查找树、平衡二叉树查找，插入元素、删除元素。

3. 堆弹出一个元素，最后一个元素弥补上来然后下沉到底。堆插入一个元素，插如到堆右下角，一路往上窜。

4. 快速排序空间复杂度，压栈就是树的最大高度。

5. 通常对二叉树进行dfs的空间复杂度。

6. 快速幂，自身迭代快速到达指定的数字。

7. gcd 欧几里得的辗转相除

O(n^0.5)

1. 判断一个数是否是质数，只需要从1判断到根号下他自己就可以了。有待证明。

2. 一些不常见的特殊的数学题目。

O(n log log n)

1. 素数筛

2. 欧拉筛

O(n)

1. 遍历数组：顺序查找、参数是数组的max、min函数

2. 桶排序

3. 字符串生成Counter哈希表

4. 借助辅助数组的空间复杂度，归并排序。

5. kmp算法生成next数组，以及匹配。

O(nlogn)

1. 对长度为n的数组进行高效的排序：经典三大nlogN级别：快排，堆排，归并。

2. 贪心题目的时间复杂度多为此。因为通常需要排序。

3. 克鲁斯卡尔根据图的边生成最小生成树，边的数量N，时间复杂度NlogN。

O(n^2)

1. 低效率的排序：冒泡排序、选择排序

2. 排序的最差情况：插入排序最差情况。不带随机效果的快速排序最差情况

3. 遍历所有二元对：数据两两比较

4. 普里姆的最小生成树算法。节点为n

5. 二维dp填表，网格路径问题，两个数组的最长公共子序列问题dp解

O(n^3)

1. 遍历3D世界所有方块，就是三维数组

2. 三维dp。dp问题的时间复杂度一般都是多项式级别。不会成为指数级别。

O(2^n)

1. 糟糕的递归：斐波那契，汉诺塔

O(n!)

1. 全排列的所有可能

2. 猴子排序的可能时间复杂度

补充：Stirling公式

O(n^n)

和上一个是等价无穷大

1. 决策树的深度成为了变量n，分叉数量也成了变量n。