※ 引述《bigmoun (123)》之銘言： : ※ 引述《reader (讀者)》之銘言： : : 演算法的複雜度有兩種，一種是計算所需時間，一種是程式碼長度。 : ????? : 這是指程式執行期間所需的空間大小嗎？ : 一般探討的不是time complexity 和 space complexity? : program length倒是還沒看過耶！ 對喔，忘記講 space complexity... 不過這可以合併起來稱為 computational complexity (計算複雜度) algorithmic comlexity (演算複雜度) 是真的少見，但確實是 重要的複雜度議題，或者可以說，這才是對演算法的複雜度的 研究。 這部分最有名的就數 computable number (可數數) 問題了， 例如以下的可數數: 0.12345678910111213141516... 這叫 Champernowne's Constant (以 10 為底，記為 C10). 它是無理數卻是可數數，只需要一個廻圈就能完成。 另外像是數列問題，如以下的著名智力測驗問題： 1 11 21 1211 111221 312211 13112221 .... 這個數列用程式很容易做，卻不能用單一多項式函數完成。 通常這算是數學領域，電腦科學比較少談，大部分都是指用 Turing Machine 計算和輸出時，需要多少步驟才能完成。 另外有不同領域但其實差不多的 program analysis 和 logical depth. 其中 program analysis 就真的是研究最短的程式碼長度了。由於它 比較不會陷入函數分析或 Turing Machine 中，看起來比較像電腦科學 領域的東西。 至於 logical depth 好像是硬體領域的東西，我不太了解，它主要是 用資訊理論來分析的，用在處理一個物理系統的複雜度，但也可以和 演算法對應。我是硬體白痴，如果說錯就請其他人補充。 --

※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 61.222.173.26