常用时间复杂度整理
按数量级递增排列，常见的时间复杂度有：
常数阶O(1),对数阶O(log2n),线性阶O(n),
线性对数阶O(nlog2n),平方阶O(n^2)，立方阶O(n^3),...，
k次方阶O(n^k),指数阶O(2^n)。随着问题规模n的不断增大，上述时间复杂度不断增大，算法的执行效率越低。
时间复杂度：基本操作重复执行的次数的阶数 T(n)=o(f(n)) 以下六种计算算法时间的多项式是最常用的。其关系为： O(1)<O(logn)<O(n)<O(nlogn) <O(n2)<O(n3) 指数时间的关系为： O(2n)<O(n!)<O(nn) 当n取得很大时，指数时间算法和多项式时间算法在所需时间上非常悬殊。
以下是一些常见时间复杂度的例子。
| 名称 | 复杂度类 |
运行时间（ |
运行时间举例 | 算法举例 |
|---|---|---|---|---|
| 常数时间 | 10 | 判断一个二进制数的奇偶 | ||
| 反阿克曼时间 | 并查集的单个操作的平摊时间 | |||
| 迭代对数时间 | en:Cole-Vishkin algorithm | |||
| 对数对数时间 | 有界优先队列的单个操作[1] | |||
| 对数时间 | DLOGTIME | 二分搜索 | ||
| 幂对数时间 | ||||
| （小于1次）幂时间 | K-d树的搜索操作 | |||
| 线性时间 | 无序数组的搜索 | |||
| 线性迭代对数时间 | Raimund Seidel的三角分割多边形算法 | |||
| 线性对数时间 | 最快的比较排序 | |||
| 二次时间 | 冒泡排序、插入排序 | |||
| 三次时间 | 矩阵乘法的基本实现，计算部分相关性 | |||
| 多项式时间 | P | 线性规划中的en:Karmarkar's algorithm，AKS质数测试 | ||
| 准多项式时间 | QP |
|
关于有向斯坦纳树问题最著名的 |
|
| 次指数时间（第一定义） | SUBEXP | Assuming complexity theoretic conjectures, BPP is contained in SUBEXP.[2] | ||
| 次指数时间（第二定义） | 2o(n） | 2n1/3 | Best-known algorithm for integer factorization and graph isomorphism | |
| 指数时间 | E | 2O(n) | 1.1n, 10n | 使用动态规划解决旅行推销员问题 |
| 阶乘时间 | O(n!) | n! | 通过暴力搜索解决旅行推销员问题 | |
| 指数时间 | EXPTIME | 2poly(n) | 2n, 2n2 | |
| 双重指数时间 | 2-EXPTIME | 22poly(n) | 22n | Deciding the truth of a given statement in Presburger
arithmetic |
常用时间复杂度如图：