跳转到内容

计算时间

维基百科,自由的百科全书

计算复杂度理论中,计算时间是种计算抽象机器必须在某些特定计算中花费的步骤数。任何抽象机器花费的计算时间都是一种用以解决计算问题计算资源。很多重要的复杂度类,都是依照在某些抽象机器上花费特定量级的计算时间而定义的。这些时间复杂度类别共想许多特征,但它们的相互关系以及复杂度类对其他计算资源的影响仍未充份明了。

最常用以度量计算时间的抽象机器就是图灵机。任何抽象机器,只要拥有

  1. 状态控制能力与
  2. 可记载状态控制磁读写头造成的计算时间的磁带

便可称做类图灵机。

因此为各类的抽象模型,我们可以定义不同的计算资源:在一个确定型图灵机上是确定型时间;在非确定型图灵机非确定型时间量子图灵机则是量子时间……等等。输入资料的计算时间等同于此输入的计算树的深度。

计算时间满足时间谱系理论,也就是说量级渐进大于的计算时间定可准许复杂度类更大的计算问题。