1
的複雜性是可以開發一種算法來估算另一種算法的時間複雜度?我的意思是,輸入的是一些算法,輸出可能是它的時間複雜度(大哦,大歐米茄,等等)。我在網上找不到任何關於它的信息。算法來估算時間的另一個算法
謝謝
的複雜性是可以開發一種算法來估算另一種算法的時間複雜度?我的意思是,輸入的是一些算法,輸出可能是它的時間複雜度(大哦,大歐米茄,等等)。我在網上找不到任何關於它的信息。算法來估算時間的另一個算法
謝謝
讓我延長@ interjay的評論一點點。
的halting problem是要求
如果能夠設計一個圖靈機(您可能覺得它在你的計算機的程序),從而給出一個圖靈機(同樣,認爲它作爲一個程序)它可以決定這個輸入圖靈機是否會最終終止。
可以證明設計這樣的圖靈機是不可能的。現在,讓我們考慮你的問題,如果你能設計一個算法,你 願意,你就可以回答給定的圖靈機是否會終止或不。這是不可能的。
以上說法被稱爲「減量化」,這是最流行的方式來顯示一個給定的問題是無法解決的。
我投票關閉這一問題作爲題外話,因爲[關於漸近運行的複雜性問題,應在cs.stackexchange.com發佈(http://meta.stackexchange.com/a/228634/287333)。 –
對不起,我不知道這件事。我會在那裏發佈。謝謝:) –
不,這是不可能寫一個算法,將所有輸入的工作。如果是這樣,你可以用它來解決暫停問題。 – interjay