: 對喔，忘記講 space complexity... 不過這可以合併起來稱為 : computational complexity (計算複雜度) : algorithmic comlexity (演算複雜度) 是真的少見，但確實是 : 重要的複雜度議題，或者可以說，這才是對演算法的複雜度的 : 研究。 : 這部分最有名的就數 computable number (可數數) 問題了， : 例如以下的可數數: : 0.12345678910111213141516... : 這叫 Champernowne's Constant (以 10 為底，記為 C10). : 它是無理數卻是可數數，只需要一個廻圈就能完成。 : 另外像是數列問題，如以下的著名智力測驗問題： : 1 : 11 : 21 : 1211 : 111221 : 312211 : 13112221 : .... : 這個數列用程式很容易做，卻不能用單一多項式函數完成。 : 通常這算是數學領域，電腦科學比較少談，大部分都是指用 Turing : Machine 計算和輸出時，需要多少步驟才能完成。 抱歉，實在不太清楚你想表達的是什麼， 而且，algorithmic complexity這個名稱好像也不多見， 還是你是想說Kolmogorov complexity? 綜觀下來，不知道你想說明的是什麼呢? : 另外有不同領域但其實差不多的 program analysis 和 logical depth. : 其中 program analysis 就真的是研究最短的程式碼長度了。由於它 : 比較不會陷入函數分析或 Turing Machine 中，看起來比較像電腦科學 : 領域的東西。 請問你文中的"program analysis"跟"函數分析"是一樣的東西嗎? 又，如果是一樣的，有這名詞的定義嗎? 我想，可能需要更精確的了解名詞後再討論。 : 至於 logical depth 好像是硬體領域的東西，我不太了解，它主要是 : 用資訊理論來分析的，用在處理一個物理系統的複雜度，但也可以和 : 演算法對應。我是硬體白痴，如果說錯就請其他人補充。 亂入一下， XD logical depth是不是在討論計算機組織的時候的data path的長度呀? 這我也完全不懂，哈哈 以上有錯請訂正。 --

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