算法來估算時間的另一個算法

Question

的複雜性是可以開發一種算法來估算另一種算法的時間複雜度？我的意思是，輸入的是一些算法，輸出可能是它的時間複雜度（大哦，大歐米茄，等等）。我在網上找不到任何關於它的信息。

謝謝

Answer 1

讓我延長@ interjay的評論一點點。

的halting problem是要求

如果能夠設計一個圖靈機（您可能覺得它在你的計算機的程序），從而給出一個圖靈機（同樣，認爲它作爲一個程序）它可以決定這個輸入圖靈機是否會最終終止。

可以證明設計這樣的圖靈機是不可能的。現在，讓我們考慮你的問題，如果你能設計一個算法，你 願意，你就可以回答給定的圖靈機是否會終止或不。這是不可能的。

以上說法被稱爲「減量化」，這是最流行的方式來顯示一個給定的問題是無法解決的。