DLOGTIME - 维基百科,自由的百科全书
此條目没有列出任何参考或来源。 (2011年4月15日) |
在複雜度理論內,DLOGTIME是一個複雜度類,其問題可以用決定型圖靈機,在對數成長的時間內解決。這是使用決定型時間,所能定義出最小且非單純(non-trivial)的複雜度類。這類複雜度一定使用隨機存取圖靈機來定義,因為機器沒有足夠的時間來讀取整個輸入(輸入的大小,成長率是O(n))。
DLOGTIME-均一性(uniformity)在電路複雜性裡面是很重要的。
詢問輸入字串的長度這個問題屬於DLOGTIME,因為我們可以對可能的輸入大小進行折半搜索演算法(binary search)。
|