时间复杂度是反映算法运行所花费的时间量，本质上计算算法的复杂度，它描述了运行一个算法需要多少计算机时间。
时间复杂度通常通过计算算法执行基本操作的数量来估计，假设每个基本操作都需要固定的时间来执行。因此，算法所花费的时间量和执行的基本操作的数量被认为最多相差一个常数因子。
由于算法的运行时间可能在相同大小的不同输入之间有所不同，因此通常会考虑算法在最坏情况的时间复杂度。这是特定大小的输入所需的最长时间。
时间复杂度概念和公式
时间复杂度可表示为输入大小的函数。因为精确计算这个函数并不容易，而且小输入的运行时间往往无关紧要，所以随着输入大小的增加，通常会专注于复杂性的行为。这是复杂性的渐近行为。正因为如此，时间复杂度一般用大O表示法来表示，一般是O(n)、O(n log n)、O(n)、O(2n)等，n是表示输入所需的输入大小。
常见的时间复杂度类型
恒定时间：O(1)
算法被认为是常数时间，如果T(n)的值受与输入大小无关的值的限制，则表示为O(1)时间。例如，访问数组中的任何单个元素都需要恒定的时间，因为只需要执行一个操作。
对数时间：O(log n)
如果T(n)=O(log n)，可以说一个算法需要对数时间。因为logan和logN由一个常数乘数关联，并且该乘数与big-O分类无关，所以对数时间算法的标准用法是O(log n)，而与T表达式中出现的对数的底数无关。
对数时间通常出现在二叉树操作和使用二分搜索算法中。
多对数时间：O((log n)k)
如果对于常数k，T(n)为O((log n)k)，则可以说算法在多对数时间内运行。这也可以写成O(logkn)。
例如，使用并行随机访问机器在多对数时间内求解矩阵链排序，并且可以在O(log3n)时间内以完全动态的方式确定每个插入/删除操作的图形是平面的。
次线性时间：o(n)
如果T(n)=o(n)，则算法在次线性时间上运行。这包括具有前面描述的时间复杂度的算法。
次线性时间算法通常是随机的，仅提供近似解。这些算法自然出现在属性测试的调查中。
线性时间：O(n)
如果算法的时间复杂度为O(n)，则可以认为该算法采用线性时间。这意味着随着输入大小的增加，运行时间最多以线性方式增加。为了更清楚地解释这一点，有一个常数c，使得对于每个大小为n的输入，运行时间最多为cn。
如果算法需要顺序读取其整个输入，那么线性时间是最佳的时间复杂度。
拟线性时间：O(n logkn)
在准线性时间（又称对数线性时间）中运行的算法对于正常数k具有T(n)=O(n logkn)，并且线性时间是k=1的情况。对于每个大于0的常数ε，它们也是O(n1+ε)。
次二次时间：o(n2)
如果一个算法有T(n)=o(n2)，那么它在次二次时间上运行。
多项式时间：O(nk)
如果算法的运行时间的上限是算法输入大小中的多项式表达式，即，对于正常数k，(n)=O(nk)，那么它在多项式时间上运行。
超多项式时间
如果T(n)的上限不是多项式，则算法在超多项式时间上运行。使用指数资源的算法显然是超多项式的，但某些算法只是相当弱的超多项式。
拟多项式时间
这些算法运行时间比多项式时间长，但不足以成为指数时间。准多项式时间算法通常出现在从NP-Hard问题到另一个问题的简化中。
次指数时间
这是当一个算法可以比任何多项式时间增长得更快，但仍远小于指数。具有次指数时间的问题比只有指数算法的问题更容易处理。
指数时间
如果一个算法的T(n)上限为2poly(n)并且poly(n)是n中的多项式，那么它在指数时间内。在确定性图灵机上承认指数时间算法的问题属于称为EXP的复杂性类别。
阶乘时间
Bogo sort是在阶乘时间上运行的算法的一个示例。
双指数时间
如果T(n)是上限22poly(n)，其中poly(n)是n中的多项式，则算法以双指数时间运行。这些算法的复杂度等级为2-EXPTIME。
