https://arolstar52-zhtest.hf.space/index.php?action=history&feed=atom&title=DLOGTIME 2026-07-07T22:54:08Z 在这个wiki上该页的修订历史 MediaWiki 1.43.8 https://arolstar52-zhtest.hf.space/index.php?title=DLOGTIME&diff=784132&oldid=prev 2015-01-10T05:30:03Z

<p></p> <p><b>新页面</b></p><div>{{unreferenced|time=2011-04-15T03:14:30+00:00}}<br /> 在[[複雜度理論]]內，&#039;&#039;&#039;DLOGTIME&#039;&#039;&#039;是一個[[複雜度類]]，其問題可以用決定型[[圖靈機]]，在[[對數]]成長的時間內解決。這是使用決定型時間，所能定義出最小且非單純（non-trivial）的複雜度類。這類複雜度一定使用[[隨機存取圖靈機]]來定義，因為機器沒有足夠的時間來讀取整個輸入（輸入的大小，成長率是O(n)）。<br /> <br /> DLOGTIME-均一性（uniformity）在[[電路複雜性]]裡面是很重要的。<br /> <br /> 詢問輸入字串的長度這個問題屬於DLOGTIME，因為我們可以對可能的輸入大小進行[[折半搜索演算法]]（binary search）。<br /> <br /> {{複雜度類}}<br /> <br /> {{DEFAULTSORT:Dlogtime}}<br /> [[Category:複雜度類]]</div>

imported>Liu116