线性时间观的特征 中西方时间观念

7151℃ BERNARD

线性时间观的特征中西方时间观念

线性时间是什么意思?

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

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

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

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

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

什么是线性时间算法

计算公式:K(N)=AO(N)+B

  线性时间

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

时间一维性

时间的一维性,就是指时间仅具有单一维度。时间是线性向前而不可逆的。

哲学史上的时间观是从实践中产生、并随着实践和科学的发展而发展的.一般地说,人们对空间的研究要比对时间的研究开始得更早一些,成果也更显著一些。当古代的几何学、力学对空间的研究已经有了相当的成绩时,而对时间的研究还几乎没有涉及。

常量时间和线性时间指什么【java

与java无关,这应该是算法的相关知识,是用来描述算法时间复杂度的。

时间复杂度,即是说你运行程序所花费的时间和你输入参数之间的关系。

比如说一个程序,要求你输入一个数N,然后打印一遍“哈哈”俩字。输入的数和打印的结果没有啥联系,但单纯的从时间复杂度的角度来看,N取1和取1000,程序的运行速度都没发生变化,因此这个就是常量时间了。

再比如说,你输入N,程序就printN遍“哈哈”,那么N=1和N=1000时,逻辑上而言程序所花费的时间应该是原先的1000倍(实际上并非如此,这是由于我们把这个计时模型抽象出来,没考虑其他因素),这就是线性时间。

初学者,回答的不太完善,有误欢迎指正。