线性时间

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

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

达到线性时间的执行效能通常是一个演算法的最佳目标[来源请求]。很多学者研究并创造了许多接近线性或更佳的演算法,包括了软体或硬体方面的研究。硬体方面,借由诸如平行运算的硬体架构,使得某些数学认为无法在标准计算模型下达到线性时间的演算法,现在都可以在线性时间内执行完毕。例如内容可定址记忆体英语Content-addressable memory)。

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

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

参阅