线性时间

在计算复杂性理论，一个被称为线性时间或 Ο（n）时间的算法，表示此算法解题所需时间正比于输入资料的大小，通常以n表示。换句话说，执行时间与输入资料大小为线性比例。例如将一列数字加总的所需时间，正比于串行的长度。

简介在计算复杂性理论，一个被称为线性时间或 Ο（n）时间的算法，表示此算法解题所需时间正比于输入资料的大小，通常以n表示。换句话说，执行时间与输入资料大小为线性比例。例如将一列数字加总的所需时间，正比于串行的长度。

然而实际情况常有差距，真实的执行时间很可能与预期的比率相差甚大，尤其在n的值很小时。在技术讨论时，在足够大的量n之下算法的执行时间从an到bn（a、b为正实数）时，就可称线性时间。详情请看大O符号。1

内容达到线性时间的执行效能通常是一个算法的最佳目标。很多学者研究并创造了许多接近线性或更佳的算法，包括了软件或硬件方面的研究。硬件方面，借由诸如平行运算的硬件架构，使得某些数学认为无法在标准计算模型下达到线性时间的算法，如今都可以在线性时间内执行完毕。例如内容可寻址内存（Content-addressable memory）。

某些排序算法可以在特殊的数据结构及排列下拥有线性时间的效率。但在一般情况下以比较元素大小来排序的算法，最多只能到达Ο（nlog（n））。最低限度复杂性的证明已被小O符号含括；通用排序算法被认为是Ω（n log（n））。另外，要找到一个集合中最大的元素是 Ω（n），因为算法必须至少比较过（n-1）次才能找到最大元素。

任何必须依赖全部输入内容才能得解的问题，它最少也得要线性时间才能得解，因为它至少得花线性时间来读取输入资料。1

常量时间在计算复杂度理论中，常量时间是一种时间复杂度，它表示某个算法求出解答的时间在固定范围内，而不依照问题输入数据大小变化。

常量时间记为（采用大O符号）。数字1可以替换为任意常数。

举例：

想在“访问数组上的元素”的问题上达到常量时间，只要以元素的序号访问即可。

然而“在数组上搜索最小值”并不是一个常量时间问题，因为这需要扫描数组上的每一个元素以寻找最小值及其位置，一般需要O(n)次访问。2

本词条内容贡献者为:

杨晓红 - 副教授 - 西南大学