計算時間

計算複雜度理論中,計算時間是種計算抽象機器必須在某些特定計算中花費的步驟數。任何抽象機器花費的計算時間都是一種用以解決計算問題計算資源。很多重要的複雜度類,都是依照在某些抽象機器上花費特定量級的計算時間而定義的。這些時間複雜度類別共想許多特徵,但它們的相互關係以及複雜度類對其他計算資源的影響仍未充份明瞭。

最常用以度量計算時間的抽象機器就是圖靈機。任何抽象機器,只要擁有

  1. 狀態控制能力與
  2. 可記載狀態控制磁讀寫頭造成的計算時間的磁帶

便可稱做類圖靈機。

因此為各類的抽象模型,我們可以定義不同的計算資源:在一個確定型圖靈機上是確定型時間;在非確定型圖靈機非確定型時間量子圖靈機則是量子時間……等等。輸入資料的計算時間等同於此輸入的計算樹的深度。

計算時間滿足時間譜系理論,也就是說量級漸進大於的計算時間定可准許複雜度類更大的計算問題。