DTIME
維基百科,自由的 encyclopedia
在計算複雜度理論內,DTIME(或者TIME)是一個圖靈機的計算資源或者計算時間的計量方式。它代表一個"普通"有實體的電腦解決特定計算問題,使用特定演算法,所要花費的時間。這個計算資源是最被廣泛研究的計算資源,因為它與真實世界所重視的資源(要花費多少時間才能計算出一個問題)息息相關。
DTIME這個資源常被使用來定義複雜度類,亦即,可以在特定時間內解決的決定性問題其集合。如果一個問題其輸入的大小為n,並且可要求f(n)的計算時間來解決,那我們說這問題在DTIME(f(n))(or TIME(f(n)))裡面。這裡沒有限制必須使用多少記憶體空間(參見計算資源),但是有可能會限制一些其他的計算資源(像是可否使用交替圖靈機)。