时间复杂度 · aiwiki.page

时间复杂度用于衡量算法执行的计算工作量，并将其表示为输入规模的函数。它并不记录算法在某台机器上实际运行了多少秒，而是在特定假设下统计操作次数，描述这一数量如何增长。在计算机科学中，时间复杂度既用于比较算法，也是计算复杂性研究的一部分；后者还研究解决计算问题所固有的资源需求。时间复杂度不同于空间复杂度，空间复杂度衡量的是计算过程中所需的内存量。(aofa.cs.princeton.edu)

输入规模与计算模型

分析首先要定义输入规模以及需要统计的操作。对于序列， $n$ 通常表示元素个数。对于矩阵，它可能表示矩阵的维数，而非矩阵元素的总数。图论中的问题往往需要分别用不同参数表示顶点数和边数。因此，涉及 $n$ 的复杂度界只有在该参数定义明确时才有意义。(live.ocw.mit.edu)

计算模型决定了基本操作的成本。基于机器字的随机访问模型将对机器字大小的数值执行某些指定操作，以及访问一个内存位置，视为常数时间操作。图灵机则通过涉及纸带的离散状态转移来衡量执行过程。这些模型为核算资源消耗提供了明确的基础，而不是对物理硬件的精确描述。(live.ocw.mit.edu)

输入的表示方式同样重要。绝对值为 $N$ 的整数用二进制表示时大约需要 $\log_2 N$ 个比特，因此，执行 $N$ 次迭代的算法，其运行时间相对于该整数的编码长度而言可能是指数级的。对任意大整数进行算术运算，通常不能视为常数时间操作：其成本取决于操作数的长度以及所执行的运算。(ocw.mit.edu)

渐近记号

时间复杂度通常使用大O记号及相关的渐近界来表示。它们描述非负运行时间函数 $T(n)$ 的增长情况，忽略常数因子以及足够小的输入：

$T(n)\in O(f(n))$ 表示存在常数 $c>0$ 和 $n_0$ ，使得对所有 $n\geq n_0$ ，都有 $T(n)\leq cf(n)$ 。
$T(n)\in\Omega(f(n))$ 给出类似的下界。
$T(n)\in\Theta(f(n))$ 表示上述上界和下界同时成立，从而给出渐近紧确的刻画。(live.ocw.mit.edu)

例如， $3n^2+7n+12$ 属于 $\Theta(n^2)$ 。它也属于 $O(n^3)$ ，但这个上界提供的信息较少。因此，大O记号不一定指出确切的增长阶。它本身也不意味着“最坏情况”：只要相应的运行时间函数已被定义，这种记号就可以描述最好情况、平均情况或其他情况下的运行时间。(live.ocw.mit.edu)

最坏情况、平均情况与摊还分析

规模相同的输入可能需要不同的计算工作量。最坏情况复杂度考察给定规模的所有输入中的最大成本，最好情况复杂度则考察最小成本。平均情况复杂度是在指定的输入概率分布下计算成本的期望值；如果没有给出这一分布，“平均输入”就不是一个精确的数学假设。(aofa.cs.princeton.edu)

对于随机化算法，期望运行时间也可以是在输入固定的情况下，对算法内部的随机选择取平均。这将算法引入的随机性与关于输入生成方式的假设区分开来。(algs4.cs.princeton.edu)

摊还分析研究一系列操作的总成本。例如，向可动态调整容量的数组末尾追加元素时，偶尔需要复制所有已存储的元素。如果容量按几何级数增长，那么从空数组开始的一系列追加操作的总成本为线性，因此每次追加操作的摊还成本为常数。这是对操作序列作出的保证，既不是概率意义上的平均值，也不意味着每次操作的最坏情况成本都是常数。(cs.princeton.edu)

常见的增长阶

常见的时间复杂度界包括：

增长阶	典型示例或含义
$\Theta(1)$	在随机访问模型下访问一个数组元素
$\Theta(\log n)$	在有序数组中进行[[binary-search
$\Theta(n)$	完整扫描 $n$ 个元素
$\Theta(n\log n)$	标准的[[merge-sort
$\Theta(n^2)$	处理每一对元素
$\Theta(n^3)$	处理每一组三个元素
$\Theta(2^n)$	遍历所有子集，且对每个子集执行常数工作量的操作

这些示例都假设相应的基本操作可以在常数时间内完成。二分查找还假设有序输入已可直接访问；加载输入或对其排序需要另行计算成本。对于对数级的复杂度界，在不同的固定对数底数之间转换只会改变一个常数因子。(live.ocw.mit.edu)

对于任意固定的 $c>1$ ，固定次数的多项式界在渐近意义上都比 $c^n$ 增长得慢。不过，较高的多项式次数或较大的乘法常数，仍可能使算法在实际关心的输入规模下难以使用。(introcs.cs.princeton.edu)

推导运行时间界

分析通常需要结合操作的成本与执行次数。顺序执行的各阶段，其成本相加。对于嵌套循环，需要统计实际迭代次数，而不能仅仅计算嵌套层数：如果外层循环的迭代编号为 $i=1,\ldots,n$ ，每次对应的内层循环执行 $i$ 次，那么内层循环总共执行 $n(n+1)/2$ 次；当每次迭代的成本为常数时，总成本呈二次增长。(algs4.cs.princeton.edu)

递归算法往往会导出一个递推关系。在归并排序这样的分治法算法中，两个规模减半的子问题，加上一个线性成本的合并阶段，得到

T(n)=2T(n/2)+\Theta(n),

其基本情形耗时为常数。由此得到的时间复杂度界为 $\Theta(n\log n)$ 。分析递推关系时，必须同时计入递归调用以及递归调用之外所做的工作。(introcs.cs.princeton.edu)

含义与实际局限

时间复杂度刻画的是运行成本随输入规模变化的规律，而不是精确的执行时间。硬件、实现方式、内存访问模式以及输入特征，都会影响实际测得的性能。因此，具有相同渐近界的算法，运行速度仍可能相差很大。反过来，增长阶更低的算法，也可能因为额外开销而在小规模输入上运行得更慢。(introcs.cs.princeton.edu)

数据结构的选择会改变操作成本，进而改变算法的整体复杂度界。实测可以通过检验特定实现和工作负载下的性能来补充数学分析；但仅凭测量结果，无法确立适用于所有输入规模或所有可能输入的复杂度界。(live.ocw.mit.edu)